2016年1月10日 星期日

[FHC 2016 Qualification Round]Boomerang Constellations

我們可以枚舉兩線段的交點,然後算出這個點和其他點的距離
接著對這些距離排序
找出所有相同距離的點群,假設點群大小是n,那麼就多了n*(n-1)/2個boomerang constellation(我也不知道那是甚麼)了
加一加,當作是答案吧,真正結果等比賽結束才知道Orz
ps.最後四題全對耶真開心 :D

code:


#include<stdio.h>
#include<map>
#include<cassert>
using namespace std;
int N;
int X[2000],Y[2000];
int Sq(const int x){return x*x;}
int main()
{
    freopen("Ain.txt","r",stdin);
    freopen("out.txt","w",stdout);
    static int testcase;assert(scanf("%d",&testcase)==1);
    while(testcase--)
    {
        assert(scanf("%d",&N)==1);
        for(int i=0;i<N;i++)assert(scanf("%d%d",&X[i],&Y[i])==2);
        int ans=0;
        for(int i=0;i<N;i++)
        {
            map<int,int>dist;
            for(int j=0;j<N;j++)if(i!=j)dist[Sq(X[i]-X[j])+Sq(Y[i]-Y[j])]++;
            for(const auto &it:dist)ans+=it.second*(it.second-1)/2;
        }
        static int kase=1;
        printf("Case #%d: %d\n",kase++,ans);
    }
    assert(scanf("%d",&testcase)!=1);
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原