LA 3708 Graveyard
2024-08-30 02:36:02
题目链接:
题意:
一个周长为10000的圆上等距离分布n个点,新增加m个点, 若使所有m+n个点等距离的分布在圆上,求原来n个点的最小移动距离。
分析:
看下样例,很容易想到是固定一个点不动,移动剩下n−1个点,就是说以这个不动点为原点,顺时针放剩下的n+m−1个点。
起初想啊,算出每个点的距离之后,把这n−1个点跟他相邻的点都比较一下找个最近的点,后来看了白书的做法, zz选手表示还是觉得很巧妙的。。
他的思想是将这个圆分成n+m份,这样最后的n+m个点就分别占据着圆上的整数点,我们可以求出原始n个点的新坐标,这样距离他最近的整数点就是floor(x+0.5),把差累加即可。
但是这样会不会出现两个原始点对应同一个整数点呢?只有当两个数的差小于1的时候他们的floor(x+0.5)才有可能相等,但是由于我们把n个点均等的放在了n+m的坐标系中,所以任何两个点的距离肯定是大于1的。
最后把坐标还原回来即可。
代码:
/*************************************************************************
> File Name: la3708.cpp
> Author: jiangyuzhu
> Mail: 834138558@qq.com
> Created Time: Sat 18 Jun 2016 03:22:49 PM CST
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
const int maxn = 1e3, mod = 1e9 + 7, oo = 0x3f3f3f3f;
int main (void)
{
int n, m;
while(~scanf("%d%d", &n, &m)){
double ans = 0;
for(int i = 1; i < n; i++){
double pos = (double)i / n * (n + m);
ans += fabs(pos - floor(pos + 0.5));
}
ans = ans / (n + m) * 10000;
printf("%.4f\n", ans);
}
}
最新文章
- jQuery文件上传插件Uploadify(转)
- tomcat集群学习记录1--初识apache http server
- GitHub的.gitignore文件设置
- Vcenter server 5.5上传ISO镜像
- android 5.X之使用Palette
- 【Origin】羡旁人
- 《HTML5 and Javascript Web Apps》读书笔记要点摘录
- Altium designer入门篇-过孔不开窗
- JavaScript数组知识网络
- (原)vs2013编译成静态库
- ASP.NET中怎样才能使自己的代码运行的效率更高
- golang 实现HTTP代理和反向代理
- ubuntu系统 不能访问非系统磁盘即挂载的数据盘 Unable to access ";DATA";
- Python的GUI编程(TK)
- java-03-动手动脑
- opencv 3.2图像矩(Image Moments)
- Check access restrictions in Zabbix agent configuration
- Divide and Conquer-169. Majority Element
- Linux下使用Opencv打开笔记本摄像头
- python 面向对象(三大特性)