HDU 4631 set维护

题意：给出n有n个点，每次插入计算最小点对距离，然后把距离和求出来。

用multiset按x坐标大小维护就行了。14s 

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
struct point
{
    long long x,y;
    bool operator < (const point &m) const
    {
        if(x==m.x)
            return y<m.y;
        return x<m.x;
    }
};
multiset<point> myset;
multiset<point>::iterator it,i1,i2;
long long dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long getmin(long long m,point a)
{
    long long ans=m;
    it=myset.lower_bound(a);
    for(i1=it; i1!=myset.end(); i1++)
    {
        long long dx=a.x-i1->x;
        if(dx*dx>=ans)
            break;
        long long dy=a.y-i1->y;
        ans=min(ans,dx*dx+dy*dy);
    }
    for(i1=it; i1!=myset.begin();)
    {
        i1--;
        long long dx=a.x-i1->x;
        if(dx*dx>=ans) break;
        long long dy=a.y-i1->y;
        ans=min(ans,dx*dx+dy*dy);
    }
    myset.insert(a);
    return ans;
}
int main()
{
    int t,n;
    long long ax,ay,bx,by,cx,cy,ans,m;
    scanf("%d",&t);
    while(t--)
    {
        myset.clear();
        scanf("%d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&ax,&bx,&cx,&ay,&by,&cy);
        point a;
        a.x=bx%cx,a.y=by%cy,ans=0;
        m=1e18;
        myset.insert(a);
        for(int i=1; i<n; i++)
        {
            a.x=(a.x*ax+bx)%cx,a.y=(a.y*ay+by)%cy;
            m=getmin(m,a);
            ans+=m;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}