This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1379" #include "../template.hpp" #include "../Other/EnumerateSubset.hpp" signed main(){ int n;cin>>n; vector<int> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; auto isParallel=[&](int li,int lj,int ri,int rj){ int xl=x[li]-x[lj],yl=y[li]-y[lj]; int xr=x[ri]-x[rj],yr=y[ri]-y[rj]; return xl*yr==xr*yl; }; auto func_c=[&](int t){ return t*(t-1)/2; }; vector<ll> dp(1<<n,0); for(int bit=0;bit<(1<<n);bit++)if(__builtin_popcount(bit)%2==0){ bool f=false; rep(a,n)if((bit>>a)&1 and !f){ for(int b=a+1;b<n;b++)if((bit>>b)&1){ vector<bool> check(n,true); check[a]=false;check[b]=false; for(int c=0;c<n;c++)if(((bit>>c)&1) and check[c]){ for(int d=c+1;d<n;d++)if(((bit>>d)&1) and check[d]){ if(isParallel(a,b,c,d)){ check[c]=false; check[d]=false; } } } bool tmp=true; rep(i,n)if((bit>>i)&1)if(check[i]) tmp=false; if(tmp) f=true; } } if(f) dp[bit]=func_c(__builtin_popcount(bit)/2); } for(int bit=0;bit<(1<<n);bit++){ for(auto x:enumerate_subset(bit)) chmax(dp[bit],dp[x]+dp[bit^x]); } cout<<dp[(1<<n)-1]<<endl; return 0; }
#line 1 "test/AOJ_1379.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1379" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/AOJ_1379.test.cpp" #line 1 "Other/EnumerateSubset.hpp" vector< int > enumerate_subset(int S) { vector< int > ret; int sub = S; while (sub > 0) { ret.push_back(sub); sub = (sub - 1) & S; } return ret; } #line 6 "test/AOJ_1379.test.cpp" signed main(){ int n;cin>>n; vector<int> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; auto isParallel=[&](int li,int lj,int ri,int rj){ int xl=x[li]-x[lj],yl=y[li]-y[lj]; int xr=x[ri]-x[rj],yr=y[ri]-y[rj]; return xl*yr==xr*yl; }; auto func_c=[&](int t){ return t*(t-1)/2; }; vector<ll> dp(1<<n,0); for(int bit=0;bit<(1<<n);bit++)if(__builtin_popcount(bit)%2==0){ bool f=false; rep(a,n)if((bit>>a)&1 and !f){ for(int b=a+1;b<n;b++)if((bit>>b)&1){ vector<bool> check(n,true); check[a]=false;check[b]=false; for(int c=0;c<n;c++)if(((bit>>c)&1) and check[c]){ for(int d=c+1;d<n;d++)if(((bit>>d)&1) and check[d]){ if(isParallel(a,b,c,d)){ check[c]=false; check[d]=false; } } } bool tmp=true; rep(i,n)if((bit>>i)&1)if(check[i]) tmp=false; if(tmp) f=true; } } if(f) dp[bit]=func_c(__builtin_popcount(bit)/2); } for(int bit=0;bit<(1<<n);bit++){ for(auto x:enumerate_subset(bit)) chmax(dp[bit],dp[x]+dp[bit^x]); } cout<<dp[(1<<n)-1]<<endl; return 0; }