poj3714
テーマ:
2つの集合点の中で、最も近い点の対の距離を求めます.
アルゴリズム:
分治、uva 10245と差は多くありませんが、これは多くの標識ビットを設けています.
悲劇:qsortタイムアウト、sortはac.
2つの集合点の中で、最も近い点の対の距離を求めます.
アルゴリズム:
分治、uva 10245と差は多くありませんが、これは多くの標識ビットを設けています.
悲劇:qsortタイムアウト、sortはac.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
struct POINT
{
double x,y;
int flag;
}point[200010],temp1[100010],temp2[100010];
double dis(POINT p1, POINT p2)
{
if(p1.flag != p2.flag)
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
else
return 1e50;
}
bool cmp(POINT a, POINT b)
{
return a.x < b.x;
}
double findMin(int l, int r)
{
if (l == r)
{
return 1e50;
}
if (l == r - 1)
{
return dis(point[l], point[r]);
}
int mid =(l + r) >> 1;
double tmp1 = findMin(l,mid);
double tmp2 = findMin(mid + 1, r);
double Mindis,tmp;
int i,j;
Mindis = tmp1 < tmp2 ? tmp1 : tmp2;
int cnt1 = 0;
int cnt2 = 0;
for (i = mid; i >= l; -- i)
{
if ((point[mid].x - point[i].x) < Mindis)
{
temp1[cnt1 ++] = point[i];
}
}
for (i = mid + 1; i <= r; ++ i)
{
if ((point[i].x - point[mid].x) < Mindis)
{
temp2[cnt2 ++] = point[i];
}
}
for (i = 0; i < cnt1; ++ i)
{
for (j = 0; j < cnt2; ++ j)
{
tmp = dis(temp1[i], temp2[j]);
if (tmp < Mindis)
{
Mindis = tmp;
}
}
}
return Mindis;
}
int main()
{
int n,i,j;
double minDis;
scanf("%d", &j);
while (j -- )
{
scanf("%d", &n);
for (i = 0; i < n; ++ i)
{
scanf("%lf%lf", &point[i].x, &point[i].y);
point[i].flag = 1;
}
for (i = n; i < 2 * n; ++ i)
{
scanf("%lf%lf", &point[i].x, &point[i].y);
point[i].flag = 2;
}
n = n << 1;
sort(point, point + n, cmp);
minDis = findMin(0, n-1);
printf("%.3lf
", minDis);
}
return 0;
}