链接：http://acm.hdu.edu.cn/showproblem.php?pid=4631
题意：依次给你n个点，每次求出当前点中的最近点对，输出所有最近点对的和；
思路：按照x排序，然后用set维护，每次插入只更新当前点和插入点前后几个位置~
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAX=5e5+;
typedef long long LL;
LL ax, bx, cx, ay, by, cy;
int T, N;
struct Point
{
LL x, y;
Point(){}
Point(LL a, LL b):x(a), y(b){};
bool operator < (const Point &p)const{
return x < p.x || (x == p.x && y < p.y);
} }p[MAX];
LL sqr(LL x)
{
return x*x;
}
LL Dis( Point A, Point B )
{
return sqr(A.x-B.x)+sqr(A.y-B.y);
} void Init( )
{
LL xx=, yy=;
for( int i=; i<N; ++ i ){
xx=(xx*ax+bx)%cx;
yy=(yy*ay+by)%cy;
p[i]=Point( xx, yy );
}
}
multiset<Point>st;
multiset<Point>::iterator it1, it2, it3;
void gao(){
st.clear();
LL ans = ;
st.insert(p[]);
LL mi = 1LL<<;
for (int i = ; i < N; i++){
Point t = p[i];
st.insert(t);
it1 = it2 = it3 = st.lower_bound(t);
int k = ;
while (k--){
if (it1 != st.begin()) it1--;
if (it3 != it1){
LL d1 = Dis(t,*it1);
if (d1<mi){
mi = d1;
}
}
if (it2 != st.end()) it2++;
if (it2 != st.end() && it2!= it3){
LL d2 = Dis(t,*it2);
if (d2 < mi){
mi = d2;
}
}
}
ans += mi;
if (mi == ) break;
}
printf("%I64d\n",ans);
}
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d", &N);
scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &ax, &bx, &cx, &ay, &by, &cy);
Init();
gao();
}
return ;
}