hdu 4631（最近点对，容器）

点击打开链接

题意:

给你一个平面，每次加入一个点，当点数>=2时，求最近点对距离的平方，最后输出所有的平方和。

给你a,b,c x[0]=0;x[i]=(x[i-1]*a+b)%c

如果按照平常的方法，每次都进行分治法求最近点对，会TLE，如果利用容器，每次都对x从小到大排序，没加入一个点p，找出比p大的第一个数，然后从这个数从两边开始找，如果x*x已经大于ans了，就可以跳出来了。。最后加起来就ok了；

#include"stdio.h"

#include"string.h"

#include"algorithm"

#include"set"

#define N 500005

typedef __int64 LL;

using namespace std;

struct node

{

	LL x,y;

	bool operator<(const node &a)const

	{

		return x<a.x;

	}

};

LL x[N],y[N],n;

void fun(LL n,LL x[])

{

	LL a,b,c;

	scanf("%I64d%I64d%I64d",&a,&b,&c);

	int i=0;

	x[i]=0;

	for(i=1;i<=n;i++)

		x[i]=(x[i-1]*a+b)%c;

}

LL min(LL a,LL b)

{

	return a<b?a:b;

}

void find()

{

	LL i;

	LL ans;

	LL sum;

	LL m1,m2;

	scanf("%I64d",&n);

	fun(n,x);

	fun(n,y);

	ans=(LL)1<<60;

	sum=0;

	multiset<node>M;

	for(i=1;i<=n;i++)

	{

		node p;

		p.x=x[i];

		p.y=y[i];

		if(i>1)

		{

			multiset<node>::iterator it=M.lower_bound(p),e;

			//M.lower_bound返回指向大于（或等于）p的第一个元素的迭代器

			for(e=it;e!=M.end();e++)

			{

				m1=e->x-p.x;

				if(m1*m1>=ans)break;

				m2=e->y-p.y;

				ans=min(ans,m1*m1+m2*m2);

			}

			for(e=it;e!=M.begin();)

			{

				e--;

				m1=e->x-p.x;

				if(m1*m1>=ans)break;

				m2=e->y-p.y;

				ans=min(ans,m1*m1+m2*m2);

			}

			sum+=ans;

		}

		M.insert(p);

	}

	printf("%I64d\n",sum);

	M.clear();

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

		find();

	return 0;

}