首页 > 其他 > 详细

1.11 POJ 3714 Raid

时间:2014-01-15 23:45:55      阅读:478      评论:0      收藏:0      [点我收藏+]

http://poj.org/problem?id=3714

想巩固一下最近点对,于是去网上搜了一道据说类似的题。一看貌似果然类似,给一个点集A,一个点集B,求min(distance(x, y))(x∈A,y∈B)。想了一下,发现只需让同一点集中的点距离无穷大即可。其他同上一篇博文中的HDU1007。

bubuko.com,布布扣
 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 200010;
 6 const double INF = 10000000000000.0;
 7 struct Point{
 8     double x, y;
 9     int flag;
10 }x[MAXN];
11 int y[MAXN], z[MAXN];
12 bool cmpx(const Point& a, const Point& b)
13 {   return a.x < b.x;   }
14 bool cmpy(const int& a, const int& b)
15 {   return x[a].y < x[b].y; }
16 inline double dis(const Point a, const Point b)
17 {   return a.flag ^ b.flag ? sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)) : INF;   }
18 
19 void Merge(int z[], int y[], int l, int r, int m)
20 {
21     int i = l, j = m+1, k = l;
22     while(i <= m && j <= r)
23         if(x[z[i]].y <= x[z[j]].y)    y[k++] = z[i++];
24         else    y[k++] = z[j++];
25     while(i <= m)   y[k++] = z[i++];
26     while(j <= r)   y[k++] = z[j++];
27 }
28 
29 double close(int y[], int z[], int l, int r)
30 {
31     if(l+1 == r)
32         return dis(x[l], x[r]);
33     if(l+2 == r)
34         return min(dis(x[l], x[l+1]), min(dis(x[l+1], x[r]), dis(x[l], x[r])));
35     int m = l+r>>1;
36     for(int i=l, j=m+1, k=l ; k<=r ; k++)
37         if(y[k] > m)    z[j++] = y[k];
38         else    z[i++] = y[k];
39     double res = min(close(z, y, l, m), close(z, y, m+1, r));
40     Merge(z, y, l, r, m);
41     int rt = l;
42     for(int i=l ; i<=r ; i++)
43         if(fabs(x[y[m]].x - x[y[i]].x) < res)
44             z[rt++] = y[i];
45     for(int i=l ; i<rt ; i++)
46         for(int j=i+1 ; j<rt ; j++)
47         {
48             if(x[z[j]].y - x[z[i]].y >= res)  break;
49             res = min(res, dis(x[z[j]], x[z[i]]));
50         }
51     return res;
52 }
53 
54 int main()
55 {
56     // freopen("input", "r", stdin);
57     int t, n;  scanf("%d", &t);
58     while(t--)
59     {
60         scanf("%d", &n);
61         for(int i=0 ; i<n ; i++)
62             scanf("%lf %lf", &x[i].x, &x[i].y), x[i].flag = 0, y[i] = i;
63         for(int i=n ; i<n<<1 ; i++)
64             scanf("%lf %lf", &x[i].x, &x[i].y), x[i].flag = -1, y[i] = i;
65         n <<= 1;
66         sort(x, x+n, cmpx);
67         sort(y, y+n, cmpy);
68         printf("%.3lf\n", close(y, z, 0, n-1));
69     }
70 }
View Code

TLE了几次是因为忘记65行的把n乘2了。。。

手多抖了一下,去网上搜,发现毁三观了:http://blog.renren.com/share/262032317/14534482490

想了一下确实有道理,如果存在一个点对的距离为无穷大,就无法得出O(nlogn)的做法

随机化算法不会,所谓的voronoi图更没听说过。。。。只能用分治假装O(nlogn)混过去了,反正poj数据弱~。~

1.11 POJ 3714 Raid

原文:http://www.cnblogs.com/holiday2014/p/3515437.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!