閱讀120 返回首頁    go 阿裏雲 go 技術社區[雲棲]

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;
}



最後更新：2017-04-03 16:48:47

  上一篇：go C# 網絡編程之網頁簡單下載實現
  下一篇：go android 滑動菜單SlidingMenu的實現