HDu 1007 Quoit Design(最近接ポイントペア)

最近接ポイントペア
Quoit Design
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25147    Accepted Submission(s): 6685
Problem Description
Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.
 
Input
The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.
 
Output
For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places. 
 
Sample Input

   
   
   
   

    
    
    
    2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0.71
0.00
0.75
   
   
   
   

 
いくつかの点の座標を与えて、それから最も近い点の対の間の距離を求めて、出力の結果はこの距離の1/2です;
解題の構想:暴力で順次各点対を遍歴して提出し始め、TLEに戻った.その後、実際にソートした後、各点の後ろの10点を遍歴すればいいことに気づき、時間を大幅に節約しました.この方法は変に見えますが.しかし、その後、私は黒書「アルゴリズム導論」の8章でこの方法を見て、この方法の正しさを証明しました.実はソートしてから、各点の後の7つの点を遍歴すればいいのです.他にも方法があって、怠け者で、書いていません.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
    double x,y;
}p[100010];
bool cmp(point a,point b)
{
    if(a.x<b.x)
        return true;
    if(a.x==b.x)
        if(a.y<b.y)
            return true;
    return false;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n==0)break;
        double min=9999999;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        sort(p,p+n,cmp);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<i+10&&j<n;j++)
            {
                double len;
                len=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
                if(len<min)
                    min=len;
            }
        }
        printf("%.2lf
",double(min/2.0));
    }
    return 0;
}

その後、テンプレートでもう一度作りました(厳密ですが、長い感じです)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
const double MAX = 10e100, eps = 0.00001;
struct Point { double x, y; int index; };
Point a[N], b[N], c[N];
double closest(Point *, Point *, Point *, int, int);
double dis(Point, Point);
int cmp_x(const void *, const void*);
int cmp_y(const void *, const void*);
int merge(Point *, Point *, int, int, int);
inline double min(double, double);
int main(){
int n, i;
double d;
while (~scanf("%d", &n)) {
if(!n)break;
for (i = 0; i < n; i++)
scanf("%lf%lf", &(a[i].x), &(a[i].y));
qsort(a, n, sizeof(a[0]), cmp_x);
for (i = 0; i < n; i++)
a[i].index = i;
memcpy(b, a, n *sizeof(a[0]));
qsort(b, n, sizeof(b[0]), cmp_y);
d = closest(a, b, c, 0, n - 1);
printf("%.2lf
", d/2.0);
}
return 0;
}
double closest(Point a[],Point b[],Point c[],int p,int q){
if (q - p == 1) return dis(a[p], a[q]);
if (q - p == 2) {
double x1 = dis(a[p], a[q]);
double x2 = dis(a[p + 1], a[q]);
double x3 = dis(a[p], a[p + 1]);
if (x1 < x2 && x1 < x3) return x1;
else if (x2 < x3) return x2;
else return x3;
}
int i, j, k, m = (p + q) / 2;
double d1, d2;
for (i = p, j = p, k = m + 1; i <= q; i++)
if (b[i].index <= m) c[j++] = b[i];
//  c            ,   y    .
else c[k++] = b[i];
d1 = closest(a, c, b, p, m);
d2 = closest(a, c, b, m + 1, q);
double dm = min(d1, d2);
//  c        y     ,      b.
merge(b, c, p, m, q);
for (i = p, k = p; i <= q; i++)
if (fabs(b[i].x - b[m].x) < dm) c[k++] = b[i];
//            dm   ,     y    .
for (i = p; i < k; i++)
for (j = i + 1; j < k && c[j].y - c[i].y < dm; j++){
double temp = dis(c[i], c[j]);
if (temp < dm) dm = temp;
}
return dm;
}
double dis(Point p, Point q){
double x1 = p.x - q.x, y1 = p.y - q.y;
return sqrt(x1 *x1 + y1 * y1);
}
int merge(Point p[], Point q[], int s, int m, int t){
int i, j, k;
for (i=s, j=m+1, k = s; i <= m && j <= t;) {
if (q[i].y > q[j].y) p[k++] = q[j], j++;
else p[k++] = q[i], i++;
}
while (i <= m) p[k++] = q[i++];
while (j <= t) p[k++] = q[j++];
memcpy(q + s, p + s, (t - s + 1) *sizeof(p[0]));
return 0;
}
int cmp_x(const void *p, const void *q){
double temp = ((Point*)p)->x - ((Point*)q)->x;
if (temp > 0) return 1;
else if (fabs(temp) < eps) return 0;
else return - 1;
}
int cmp_y(const void *p, const void *q){
double temp = ((Point*)p)->y - ((Point*)q)->y;
if (temp > 0) return 1;
else if (fabs(temp) < eps) return 0;
else return - 1;
}
inline double min(double p, double q)
{
return (p > q) ? (q): (p);
}