Light OJ 1018 / Bitmask DP

/***
 created: 2022-01-28-23.13.14
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll Set(ll N,ll pos){return N=N|(1<<pos);}
ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
bool check(ll N,ll pos){return (bool)(N & (1<<pos));}

ll dp[(1<<16)+2],clinear[20][20];

ll x[20],y[20],n;

ll solve(ll mask)
{
     if(dp[mask]!=-1) return dp[mask];

     if(mask==(1<<n)-1) return 0;

     if(mask==(1<<(n-1))-1 || mask==(1<<(n-2))-1) return 1;

     ll ans=1e5;

     for(ll i=0;i<n;i++)
     {
          if(check(mask,i)==0)
          {
               for(ll j=i+1;j<n;j++)
               {
                    if(check(mask,j)==0)
                    {
                         ans=min(ans,1+solve(mask|clinear[i][j]));
                    }
               }
               break;
          }
     }

     return dp[mask]=ans;
}

bool colinear(ll i,ll j,ll k)
{
     if((x[i]*y[j])+(x[j]*y[k])+(x[k]*y[i])==(x[i]*y[k])+(x[k]*y[j])+(x[j]*y[i])) return 1;
     return 0;
}

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);

   test
   {
        cin>>n;

        for(ll i=0;i<n;i++)
        {
             cin>>x[i]>>y[i];
        }

        memset(dp,-1,sizeof dp);
        memset(clinear,0,sizeof clinear);

        for(ll i=0;i<n;i++)
        {
             for(ll j=i+1;j<n;j++)
             {
                  for(ll k=0;k<n;k++)
                  {
                       if(colinear(i,j,k)==1)
                       {
                            clinear[i][j]|=(1ll<<k);
                       }
                  }
             }
        }
        cout<<"Case "<<cs<<": "<<solve(0)<<nl;
   }



   get_lost_idiot;
}