题意:一个空平面,每次增加一个点,
其坐标根据上一个点算出:(x[i-1] * Ax + Bx ) mod Cx,(y[i-1] * Ay + By ) mod Cy
求出现有点集中的最近点对的距离的平方,共增加n个点,求每次求得的平方的和
http://blog.csdn.net/liuledidai/article/details/9664031
/* 每次对于一个新插入的点,找出x与之最近的,然后分别向两侧搜 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<set> #include<math.h> using namespace std; typedef long long int64; //typedef __int64 int64; const int maxn = 5e5+5; const int64 inf = 999999999999; const double pi=acos(-1.0); const double eps = 1e-8; struct Node{ int64 x,y; }; Node cur,nxt; typedef pair<int64,int64> PII; #define MP(a,b) make_pair((a),(b)) set< pair<int64,int64> > s; int main(){ int T; scanf("%d",&T); while( T-- ){ int64 Ax,Bx,Cx,Ay,By,Cy; int n; scanf("%d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&Ax,&Bx,&Cx,&Ay,&By,&Cy); //scanf("%d%lld%lld%lld%lld%lld%lld",&n,&Ax,&Bx,&Cx,&Ay,&By,&Cy); s.clear(); cur.x = cur.y = 0; nxt.x = (Ax*cur.x+Bx)%Cx; nxt.y = (Ay*cur.y+By)%Cy; cur = nxt; s.insert( MP(cur.x,cur.y) ); n--; int64 res,Min; res = 0; Min = inf; while( n-- ){ if( Min==0 ) break; nxt.x = (Ax*cur.x+Bx)%Cx; nxt.y = (Ay*cur.y+By)%Cy; cur = nxt; if( s.count(MP(cur.x,cur.y)) ) { res += 0; break; } s.insert( MP(cur.x,cur.y) ); set<PII>::iterator it,tmp; it = s.lower_bound( MP(cur.x,cur.y) ); for( tmp=it,tmp++;tmp!=s.end();tmp++ ){ int64 tx = (*tmp).first; int64 ty = (*tmp).second; if( (tx-cur.x)*(tx-cur.x)>=Min ) break; else{ int64 Dis = (tx-cur.x)*(tx-cur.x)+(ty-cur.y)*(ty-cur.y); Min = min( Min,Dis ); } } for( tmp=it,tmp--;it!=s.begin();tmp-- ){ int64 tx = (*tmp).first; int64 ty = (*tmp).second; if( (tx-cur.x)*(tx-cur.x)>=Min ) break; else{ int64 Dis = (tx-cur.x)*(tx-cur.x)+(ty-cur.y)*(ty-cur.y); Min = min( Min,Dis ); } if( tmp==s.begin() ) break; } res += Min; } //printf("%lld\n",res); printf("%I64d\n",res); } return 0; }