lightoj1018

CODE

#include <iostream>
#include <cstring>
int nCase;
#define CL(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf = 0x3f3f3f3f;
int line[20][20],x[20],y[20],dp[1<<16],n;

int dfs(int s)
{
        if(dp[s]!=inf)return dp[s];
        int num = 0;
        for(int i=0;i<16;i++)
                if(s&(1<<i))num++;
        if(num<=2)return dp[s]=1;
        int i =0 ;
        while(!(s&(1<<i)))i++;
        for(int j=i+1;j<n;j++)
        {
                if(s&(1<<j))
                        dp[s]=min(dp[s],dfs(s&(~line[i][j]))+1);
        }
        return dp[s];
}
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                cin >> n;
                for(int i=0;i<n;i++)
                        cin >>x[i]>>y[i];
                CL(line,0);
                CL(dp,0x3f);
                dp[0]=0;
                for(int i=0;i<n;i++)
                        for(int j=i+1;j<n;j++)
                {
                        line[i][j]=(1<<i)|(1<<j);
                        int dx1=x[j]-x[i],dy1=y[j]-y[i];
                        for(int k=j+1;k<n;k++)
                        {
                                int dx2=x[k]-x[i],dy2=y[k]-y[i];
                                if(dx2*dy1==dy2*dx1)
                                        line[i][j]|=(1<<k);
                        }
                        line[j][i]==line[i][j];
                }
                cout <<"Case "<<++nCase<<": "<<dfs((1<<n)-1)<<endl;
        }

        return 0;
}