hdu4631Sad Love Story(多校3）（最接近点对）

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

比赛的时候搜到了最接近点对的求法 Nlog(N）又估摸着依次插入求的话会TLE 想了想觉得可以先把最近的位置求出来然后后面的直接不用求了依次直到减完又觉得可能会有变态的数据每次最近的都在最后面没敢写。。后来发现它出现在题解的方法三中。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 using namespace std;
  7 #define  N 500005
  8 #define LL long long
  9 #define INF  1000000000000000000
 10 int mm;
 11 LL d;
 12 struct Point
 13 {
 14     LL x;
 15     LL y;
 16     int p;
 17 }point[N],tt[N];
 18 int tmpt[N];
 19 
 20 bool cmpxy(const Point& a, const Point& b)
 21 {
 22     if(a.x != b.x)
 23         return a.x < b.x;
 24     return a.y < b.y;
 25 }
 26 bool cmpy(const int& a, const int& b)
 27 {
 28     return point[a].y < point[b].y;
 29 }
 30 
 31 LL min(LL a, LL b)
 32 {
 33     return a < b ? a : b;
 34 }
 35 
 36 LL dis(int i, int j)
 37 {
 38     return (point[i].x-point[j].x)*(point[i].x-point[j].x)
 39                 + (point[i].y-point[j].y)*(point[i].y-point[j].y);
 40 }
 41 void Closest_Pair(int left, int right)
 42 {
 43     if(left==right)
 44     {
 45         return ;
 46     }
 47     if(left + 1 == right)
 48     {
 49          LL xx = dis(left, right);
 50          if(d>xx)
 51          {
 52 
 53              d = xx;
 54              mm = max(point[left].p,point[right].p);
 55          }
 56          return ;
 57      }
 58     int mid = (left+right)>>1;
 59     Closest_Pair(left,mid);
 60     Closest_Pair(mid+1,right);
 61     int i,j,k=0;
 62     for(i = left; i <= right; i++)
 63     {
 64         if((point[mid].x-point[i].x)*(point[mid].x-point[i].x) <= d)
 65             tmpt[k++] = i;
 66     }
 67     sort(tmpt,tmpt+k,cmpy);
 68     for(i = 0; i < k; i++)
 69     {
 70         for(j = i+1; j < k && (point[tmpt[j]].y-point[tmpt[i]].y)*(point[tmpt[j]].y-point[tmpt[i]].y)<d; j++)
 71         {
 72             LL d3 = dis(tmpt[i],tmpt[j]);
 73             if(d > d3)
 74             {
 75                  d = d3;
 76                  mm = max(point[tmpt[j]].p,point[tmpt[i]].p);
 77             }
 78         }
 79     }
 80 }
 81 int main()
 82 {
 83     int t,a[10],i;
 84     cin>>t;
 85     while(t--)
 86     {
 87         for(i = 1; i <= 7 ; i++)
 88         cin>>a[i];
 89         point[i].x = 0;
 90         point[i].y = 0;
 91         for(i = 1; i <= a[1] ; i++)
 92         {
 93             point[i].x = (point[i-1].x*a[2]+a[3])%a[4];
 94             point[i].y = (point[i-1].y*a[5]+a[6])%a[7];
 95             point[i].p = i;
 96             tt[i].x = point[i].x;
 97             tt[i].y = point[i].y;
 98             tt[i].p = i;
 99         }
100         LL s=0;
101         int n = a[1];
102         while(1)
103         {
104             sort(point+1,point+n+1,cmpxy);
105             d = INF;
106             Closest_Pair(1,n);
107             s+=(n-mm+1)*d;
108             n = mm-1;
109             for(i = 1 ; i <= n ; i++)
110             {
111                 point[i].x = tt[i].x;
112                 point[i].y = tt[i].y;
113                 point[i].p = tt[i].p;
114             }
115             if(n<=1)
116             break;
117         }
118         cout<<s<<endl;
119     }
120     return 0;
121 }

View Code