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 ;
}