415
ZOJ 2107 HDU 1007 最近点对
题意：给出100000以内个点，求出最近一对点的距离，然后除以2输出。
点数较多不能枚举，运用分治思想，先按照x排序，选出与当前点距离小于当前最优值的，再y排序更新最优值。按照这个思想写完3400ms，上网找了个优化到400+ms的。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 100005
struct point
{
double x,y;
} p[maxn],p1[maxn];
int cmpx(point a,point b)
{
return a.x<b.x;
}
int cmpy(point a,point b)
{
return a.y<b.y;
}
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double getmin(int l,int r)
{
double ans;
if(l>=r)return 1e30;
if(l+1==r) return dis(p[l],p[r]);
int m=(l+r)>>1;
ans=min(getmin(l,m),getmin(m+1,r));
int cn=0;
for(int i=l; i<=r; i++)
if(fabs(p[i].x-p[m].x)<ans)
p1[cn++]=p[i];
sort(p1,p1+cn,cmpy);
for(int i=0; i<cn; i++)
for(int j=i+1; j<cn&&p1[j].y-p1[i].y<ans; j++)
ans=min(ans,dis(p1[i],p1[j]));
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n),n)
{
for(int i=0; i<n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p,p+n,cmpx);
printf("%.2f\n",getmin(0,n-1)/2);
}
return 0;
}
400ms+的 不知道差别在哪 思想差不多比我优化的好吧。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX = 100050;
const double oo = 1e100;
const double eps = 1e-8;
struct Point
{
double x, y;
Point()
{
}
Point(double x, double y) :
x(x), y(y)
{
}
Point operator+(const Point& p) const
{
return Point(x + p.x, y + p.y);
}
Point operator-(const Point& p) const
{
return Point(x - p.x, y - p.y);
}
double operator*(const Point& p) const
{
return x * p.y - y * p.x;
}
double operator&(const Point& p) const
{
return x * p.x + y * p.y;
}
double norm()
{
return sqrt(x * x + y * y);
}
void init()
{
scanf("%lf%lf", &x, &y);
}
};
bool cmp1(const Point& a, const Point& b)
{
return a.x < b.x;
}
bool cmp2(const Point& a, const Point& b)
{
return a.y < b.y;
}
Point p[MAX];
Point s1[MAX >> 1], s2[MAX >> 1];
double dfs(int l, int r)
{
int mid, top1, top2, t;
double d1, d2, d, m;
if (l >= r)
return oo;
if (l + 1 == r)
{
return (p[l] - p[r]).norm();
}
mid = l + r >> 1;
d1 = dfs(l, mid);
d2 = dfs(mid + 1, r);
d = min(d1, d2);
m = (p[mid].y + p[mid + 1].y) / 2;
top1 = top2 = 0;
for (int i = mid; i >= l; i--)
{
if (p[i].y >= m - d)
{
s1[top1++] = p[i];
}
else
{
break;
}
}
for (int i = mid + 1; i <= r; i++)
{
if (p[i].y <= m + d)
{
s2[top2++] = p[i];
}
else
{
break;
}
}
sort(s1, s1 + top1, cmp1);
sort(s2, s2 + top2, cmp1);
for (int tmp = 0, i = 0; i < top1; i++)
{
while (tmp >= 0 && s2[tmp].x >= s1[i].x - d)
tmp--;
tmp++;
for (t = tmp; s2[t].x <= s1[i].x + d && t < top2; t++)
{
d = min(d, (s1[i] - s2[t]).norm());
}
tmp = t - 1;
}
return d;
}
int main()
{
int n;
while (scanf("%d", &n), n)
{
for (int i = 0; i < n; i++)
{
p[i].init();
}
sort(p, p + n, cmp2);
printf("%.2f\n", dfs(0, n - 1) / 2.0);
}
return 0;
}
最后更新：2017-04-03 16:48:43