http://acm.hdu.edu.cn/showproblem.php?pid=4631
没想到这道题需要用“平均时间复杂度” 计算 一直没有想到解法 因为不符考虑了最坏情况的理念
方法一：
每加一个点 就找x值和它接近的 有可能更新最小距离的点进行判断更新 运行的相当的快 无语
方法二：
每求出所有点的最近点对 假如说是p[i],p[j](i<j) 那么在j之后加上的点不影响最小距离
递归j前面的所有点就可以了
由于自己的 求最近点对算法 写的相当烂 所有跑的相当慢，勉强过
代码1和代码2：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<double,double>ppd;
const double PI = acos(-1.);
const double eps = (1e-9);
const int N=1000010;
vector<int>vt[N];
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
for(int i=0;i<N;++i)
vt[i].clear();
int n;
scanf("%d",&n);
int A1,B1,C1,A2,B2,C2;
cin>>A1>>B1>>C1;
cin>>A2>>B2>>C2;
int x=0,y=0;
ll ans=0;
ll tmp=(ll)(1e13);
for(int i=1;i<=n;++i)
{
x=((ll)A1*x+B1)%C1;
y=((ll)A2*y+B2)%C2;
for(int i=0;x+i<=1000000;++i)
{
ll x1=(ll)i*i;
if(x1>=tmp)
break;
for(unsigned int j=0;j<vt[x+i].size();++j)
tmp=min(tmp,x1+(ll)(y-vt[x+i][j])*(y-vt[x+i][j]));
}
for(int i=-1;x+i>=0;--i)
{
ll x1=(ll)i*i;
if(x1>=tmp)
break;
for(unsigned int j=0;j<vt[x+i].size();++j)
tmp=min(tmp,x1+(ll)(y-vt[x+i][j])*(y-vt[x+i][j]));
}
vt[x].push_back(y);
if(tmp!=(ll)(1e13))
ans+=tmp;
}
cout<<ans<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int>pp;
const double PI = acos(-1.);
const double eps = (1e-9);
const int N=1000010;
pp p[N];
struct node
{
int x,y;
int index;
}a[N],b[N];
ll dist(const node &a,const node &b)
{
return (ll)(a.x-b.x)*(a.x-b.x)
+(ll)(a.y-b.y)*(a.y-b.y);
}
bool cmpx(const node &a,const node &b)
{
return a.x<b.x;
}
bool cmpy(const node &a,const node &b)
{
return a.y<b.y;
}
ll dfs(int l,int r,int &k)
{
if(r-l==1)
{k=max(a[l].index,a[r].index);return dist(a[l],a[r]);}
int m=(l+r)>>1;
int k1,k2;
ll d;
ll d1=dfs(l,m,k1);
ll d2=dfs(m,r,k2);
if(d1<d2) {d=d1;k=k1;}
else {d=d2;k=k2;}
int ln=0,M=(int)(sqrt(1.0*d));
for(int i=m+1;i<=r&&a[i].x-a[m].x<=M;++i)
{b[ln]=a[i];++ln;}
for(int i=m-1;i>=l&&a[m].x-a[i].x<=M;--i)
{b[ln]=a[i];++ln;}
sort(b,b+ln,cmpy);
for(int i=0;i<ln;++i)
for(int j=1;j<=7&&i+j<ln;++j)
if(dist(b[i],b[i+j])<d)
{d=dist(b[i],b[i+j]);k=max(b[i].index,b[i+j].index);}
return d;
}
ll solve(int n)
{
ll ans=0;
int r=n;
while(r>=2)
{
for(int i=1;i<=r;++i)
{a[i].x=p[i].first;a[i].y=p[i].second;a[i].index=i;}
sort(a+1,a+r+1,cmpx);
int k;
ll tmp=dfs(1,r,k);
ans+=tmp*(r-k+1);
r=k-1;
}
return ans;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int A1,B1,C1,A2,B2,C2;
scanf("%d %d %d",&A1,&B1,&C1);
scanf("%d %d %d",&A2,&B2,&C2);
p[0].first=0,p[0].second=0;
for(int i=1;i<=n;++i)
{
p[i].first=((ll)A1*p[i-1].first+B1)%C1;
p[i].second=((ll)A2*p[i-1].second+B2)%C2;
}
cout<<solve(n)<<endl;
}
return 0;
}