暑假集训Day23 B (dfs+几何)

题目链接在这里：2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MAX=25;
 5 LL n,ans,x[MAX],y[MAX],used[MAX],cnt;
 6 bool vis[MAX];
 7 LL gcd(LL xx,LL yy){return yy==0?xx:gcd(yy,xx%yy);}
 8 pair <LL,LL> k[MAX];
 9 bool cmp(pair<LL,LL> xx,pair<LL,LL> yy){
10     if (xx.first!=yy.first) return xx.first<yy.first;
11     return xx.second<yy.second;
12 }
13 void check(){
14     LL i,j,zt,zt2,gg;
15     zt2=0,cnt=0;
16     pair <LL,LL> kk;
17     memset(vis,false,sizeof(vis));
18     for (i=1;i<=n;i++){
19         if (vis[i]) continue;
20         vis[i]=vis[used[i]]=true;
21         kk.first=y[i]-y[used[i]];
22         kk.second=x[i]-x[used[i]];
23         gg=gcd(abs(kk.first),abs(kk.second));
24         if (gg!=0) kk.first/=gg,kk.second/=gg;
25         if (kk.first<0) kk.first*=-1,kk.second*=-1;
26         if (kk.first==0) kk.second=abs(kk.second);
27         if (kk.second==0) kk.first=abs(kk.first);
28         k[++cnt]=kk;
29     }
30     //for (i=1;i<=n;i++) cout<<used[i]<<' ';cout<<endl;
31     sort(k+1,k+cnt+1,cmp);
32     //for (i=1;i<=cnt;i++) cout<<k[i].first<<' '<<k[i].second<<endl;
33     //cout<<endl;
34     zt=1;
35     for (i=2;i<=cnt+1;i++){
36         if (k[i]!=k[i-1]){
37             zt2+=zt*(zt-1)/2;
38             zt=1;
39         }
40         else zt++;
41     }
42     ans=max(ans,zt2);
43 }
44 void dfs(int a,int b){
45     if(a==n) return;
46     if(used[a]) dfs(a+1,b);
47     for(int i=a+1;i<=n;i++){
48         if((!used[i])&&(!used[a])){
49             used[a]=i;
50             used[i]=a;
51             if(b==n/2) check();
52             else dfs(a+1,b+1);
53             used[a]=0;
54             used[i]=0;
55         }
56     }
57 }
58 int main(){
59     freopen ("b.in","r",stdin);
60     freopen ("b.out","w",stdout);
61     LL i,j,gg;
62     scanf("%lld",&n);
63     for (i=1;i<=n;i++)
64         scanf("%lld%lld",x+i,y+i);
65     memset(vis,false,sizeof(vis));
66     dfs(1,1);
67     printf("%lld",ans);
68     return 0;
69