test/AOJ_1379.test.cpp

View this file on GitHub
Last update: 2024-05-17 14:55:36+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1379

Depends on

Code

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