【hdoj 1007】最近点对
发布时间：2020-12-13 20:10:22 所属栏目：PHP教程 来源：网络整理
导读：题目： 传送门 解答： 直接暴力求解肯定会超时。此题核心就是求出来最近的1对点之间的距离，即最近点对算法。 扼要来讲就是利用 分治 的思想，左半边的最小距离，与右半边的最小距离比较，得到1个mindist。再 遍历 分界限左右mindist 范围内点的间距，取最小
|
题目：传送门 解答：直接暴力求解肯定会超时。此题核心就是求出来最近的1对点之间的距离，即最近点对算法。 扼要来讲就是利用分治的思想，左半边的最小距离，与右半边的最小距离比较，得到1个mindist。再遍历分界限左右 mindist 范围内点的间距，取最小值。 这样，需要暴力的只有分界限周围的点。但是我第1次提交版本还是超时。询问以后是由于优化不够，写在trick中。 这里1些trick:
#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,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;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |