STL+暴力

Sad Love Story

2
5 765934 377744 216263 391530 669701 475509
5 349753 887257 417257 158120 699712 268352

8237503125
49959926940
Hint
If there are two points coincide,then the distance between the closest pair is simply 0.
 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

typedef long long int LL;
typedef pair<LL,LL> pII;

int T_T,n;
LL A[2],B[2],C[2],pre_x,pre_y;

LL get_next(LL x,int kind)
{
    ///0...x   1...y
    return (x*A[kind]+B[kind])%C[kind];
}

LL get_dist(LL x1,LL y1,LL x2,LL y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int main()
{
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%d%I64d%I64d%I64d%I64d%I64d%I64d",&n,A,B,C,A+1,B+1,C+1);

    LL ans=0,mindist=0x3f3f3f3f3f3f3f3fLL;
    set<pII> st;

    pre_x=get_next(0LL,0);
    pre_y=get_next(0LL,1);
    st.insert(make_pair(pre_x,pre_y));

	set<pII>::iterator it,pos,item;

    for(int i=2;i<=n;i++)
    {
        LL X,Y;
        X=get_next(pre_x,0);
        Y=get_next(pre_y,1);
		pos=st.lower_bound( make_pair(X,Y) );
		for(it=pos;it!=st.begin();)
		{
		    it--;
			if(((X-(*it).first)*(X-(*it).first))>=mindist) break;
			else mindist=min(mindist,get_dist(X,Y,(*it).first,(*it).second));
		}
		for(it=pos;it!=st.end();it++)
		{
			if(((X-(*it).first)*(X-(*it).first))>=mindist) break;
			else mindist=min(mindist,get_dist(X,Y,(*it).first,(*it).second));
		}
		pre_x=X,pre_y=Y;
		st.insert(make_pair(X,Y));
        ans+=mindist;
    }
    printf("%I64d\n",ans);
}
	return 0;
}

HDOJ 4631 Sad Love Story,布布扣,bubuko.com

HDOJ 4631 Sad Love Story

原文：http://blog.csdn.net/u012797220/article/details/22412975