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

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

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define  N 500005

 #define LL long long

 #define INF  1000000000000000000

 int mm;

 LL d;

 struct Point

 {

     LL x;

     LL y;

     int p;

 }point[N],tt[N];

 int tmpt[N];

 bool cmpxy(const Point& a, const Point& b)

 {

     if(a.x != b.x)

         return a.x < b.x;

     return a.y < b.y;

 }

 bool cmpy(const int& a, const int& b)

 {

     return point[a].y < point[b].y;

 }

 LL min(LL a, LL b)

 {

     return a < b ? a : b;

 }

 LL dis(int i, int j)

 {

     return (point[i].x-point[j].x)*(point[i].x-point[j].x)

                 + (point[i].y-point[j].y)*(point[i].y-point[j].y);

 }

 void Closest_Pair(int left, int right)

 {

     if(left==right)

     {

         return ;

     }

     if(left +  == right)

     {

          LL xx = dis(left, right);

          if(d>xx)

          {

              d = xx;

              mm = max(point[left].p,point[right].p);

          }

          return ;

      }

     int mid = (left+right)>>;

     Closest_Pair(left,mid);

     Closest_Pair(mid+,right);

     int i,j,k=;

     for(i = left; i <= right; i++)

     {

         if((point[mid].x-point[i].x)*(point[mid].x-point[i].x) <= d)

             tmpt[k++] = i;

     }

     sort(tmpt,tmpt+k,cmpy);

     for(i = ; i < k; i++)

     {

         for(j = i+; j < k && (point[tmpt[j]].y-point[tmpt[i]].y)*(point[tmpt[j]].y-point[tmpt[i]].y)<d; j++)

         {

             LL d3 = dis(tmpt[i],tmpt[j]);

             if(d > d3)

             {

                  d = d3;

                  mm = max(point[tmpt[j]].p,point[tmpt[i]].p);

             }

         }

     }

 }

 int main()

 {

     int t,a[],i;

     cin>>t;

     while(t--)

     {

         for(i = ; i <=  ; i++)

         cin>>a[i];

         point[i].x = ;

         point[i].y = ;

         for(i = ; i <= a[] ; i++)

         {

             point[i].x = (point[i-].x*a[]+a[])%a[];

             point[i].y = (point[i-].y*a[]+a[])%a[];

             point[i].p = i;

             tt[i].x = point[i].x;

             tt[i].y = point[i].y;

             tt[i].p = i;

         }

         LL s=;

         int n = a[];

         while()

         {

             sort(point+,point+n+,cmpxy);

             d = INF;

             Closest_Pair(,n);

             s+=(n-mm+)*d;

             n = mm-;

             for(i =  ; i <= n ; i++)

             {

                 point[i].x = tt[i].x;

                 point[i].y = tt[i].y;

                 point[i].p = tt[i].p;

             }

             if(n<=)

             break;

         }

         cout<<s<<endl;

     }

     return ;

 }

巴特西

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

最新文章

热门文章