HDU4631+Set+最近点对

题意：一个空平面，每次增加一个点，
其坐标根据上一个点算出：(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;
}