【hdoj 1007】最近点对
来源：程序员人生 发布时间：2015-05-19 08:01:36 阅读次数：2496次
题目：传送门
解答：直接暴力求解肯定会超时。此题核心就是求出来最近的1对点之间的距离，即最近点对算法。
扼要来讲就是利用分治的思想，左半边的最小距离，与右半边的最小距离比较，得到1个mindist。再遍历分界限左右 mindist 范围内点的间距，取最小值。
这样，需要暴力的只有分界限周围的点。但是我第1次提交版本还是超时。询问以后是由于优化不够，写在trick中。
这里1些trick:
- 分界限：不1定是距离上的等分，根据 x 轴位置排序落后行数量上的等分（取最中间的点）左右更好；
- 取中点暴力时，切记不要与本身比较（距离为0）；
- 除非有 string，不然不要用 cin，scanf 会快上很多；
- 这个我1直很想吐槽……数据精度，做 oj 就别用 float 了，直接上 double（困扰我好久）；
- 浮点数（float，double）是不存在完全相等的（参见这里）。可以用eps（1般为1e⑹, 1e⑻），利用 fabs（abs是整数取绝对值）判断范围是不是小于 eps.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>
#define MAXDIST 1000000
using namespace std;
struct Point{
double x;
double y;
};
int n;
double x, y;
bool tag;
Point tmp;
double eps = 1e⑻;
Point gao[100005];
bool cmpxy (const Point a, const Point b)
{
if(a.x != b.x)
{
return a.x < b.x;
}
else
{
return a.y < b.y;
}
}
bool cmpx (const Point a, const Point b)
{
return a.x < b.x;
}
bool cmpy (const Point a, const Point b)
{
return a.y < b.y;
}
double dist(const Point a, const Point b)
{
return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double nearestPair(int head, int tail)
{
if(head == tail)
{
return MAXDIST;
}
if(head + 1 == tail)
{
return dist(gao[head], gao[tail]);
}
int mid = (head + tail) >> 1;
double d1 = nearestPair(head, mid);
double d2 = nearestPair(mid + 1, tail);
double mindist = d1 > d2 ? d2 : d1;
for(int i = head; i<=tail; i++)
{
// 不能和本身比较，否则距离为 0
if(i != mid && gao[i].x > (gao[mid].x - mindist) && gao[i].x < (gao[mid].x + mindist))
{
if(dist(gao[i], gao[mid]) < mindist)
mindist = dist(gao[i], gao[mid]);
}
}
return mindist;
}
int main()
{
while(cin>>n && n!= 0)
{
memset(gao, 0, sizeof(gao));
tag = false;
for(int i=0; i<n; i++)
{
scanf("%lf%lf", &x, &y);
tmp.x = x;
tmp.y = y;
gao[i] = tmp;
}
sort(gao, gao + n, cmpxy);
for(int i=0; i < n⑴; i++)
{
if(fabs(gao[i].x - gao[i+1].x) < eps && fabs(gao[i].y - gao[i+1].y) < eps)
tag = true;
}
if(tag)
{
cout<<"0.00"<<endl;
continue;
}
else
{
double d = nearestPair(0, n⑴);
printf("%.2f
", sqrt(d)/2);
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
