hdu 4631Sad Love Story<计算几何>

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4631

题意：依次给你n个点，每次求出当前点中的最近点对，输出所有最近点对的和；

思路：按照x排序，然后用set维护，每次插入只更新当前点和插入点前后几个位置~

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <set>
 7 using namespace std;
 8 const int MAX=5e5+10;
 9 typedef long long LL;
10 LL ax, bx, cx, ay, by, cy;
11 int T, N;
12 struct Point
13 {
14     LL x, y;
15     Point(){}
16     Point(LL a, LL b):x(a), y(b){};
17    bool operator < (const Point &p)const{
18         return x < p.x || (x == p.x && y < p.y);
19     }
20 
21 }p[MAX];
22 LL sqr(LL x)
23 {
24     return x*x;
25 }
26 LL Dis( Point A, Point B )
27 {
28     return sqr(A.x-B.x)+sqr(A.y-B.y);
29 }
30 
31 void Init( )
32 {
33     LL xx=0, yy=0;
34     for( int i=0; i<N; ++ i ){
35         xx=(xx*ax+bx)%cx;
36         yy=(yy*ay+by)%cy;
37         p[i]=Point( xx, yy );
38     }
39 }
40 multiset<Point>st;
41 multiset<Point>::iterator it1, it2, it3;
42 void gao(){
43     st.clear();
44     LL ans = 0;
45     st.insert(p[0]);
46     LL mi = 1LL<<60;
47     for (int i = 1; i < N; i++){
48         Point t = p[i];
49         st.insert(t);
50         it1 = it2 = it3 = st.lower_bound(t);
51         int k = 5;
52         while (k--){
53             if (it1 != st.begin()) it1--;
54             if (it3 != it1){
55                 LL d1 = Dis(t,*it1);
56                 if (d1<mi){
57                     mi = d1;
58                 }
59             }
60             if (it2 != st.end()) it2++;
61             if (it2 != st.end() && it2!= it3){
62                 LL d2 = Dis(t,*it2);
63                 if (d2 < mi){
64                     mi = d2;
65                 }
66             }
67         }
68         ans += mi;
69         if (mi == 0) break;
70     }
71     printf("%I64d
",ans);
72 }
73 int main()
74 {
75     scanf("%d", &T);
76     while(T--){
77         scanf("%d", &N);
78         scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &ax, &bx, &cx, &ay, &by, &cy);
79         Init();
80         gao();
81     }
82     return 0;
83 }

View Code