fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int t, n, x, y;
  4. pair<int, int> pt[17];
  5. pair<int, int> p1, p2;
  6. int mask;
  7. int mat[17][17];
  8. int mn[1<<16];
  9. int target;
  10. int calc(int mask){
  11.     //cout << mask << endl;
  12.     if(mask == target)
  13.         return 0;
  14.     if(mn[mask] != -1) return mn[mask];
  15.     int i;
  16.     for(i=0;(mask>>i)&1;i++);
  17.     i++;
  18.     int best = 16*16+500;
  19.     for(int j=1; j<=n; j++){
  20.         if(i != j){
  21.             best = min(best, calc(mask|mat[i][j])+1);
  22.         }
  23.     }
  24.     return mn[mask] = best;
  25. }
  26. int main()
  27. {
  28.     cin >> t;
  29.     for(int k=1; k<=t; k++){
  30.         cin >> n;
  31.         for(int i=1; i<=n; i++){
  32.             cin >> x >> y;
  33.             pt[i] = make_pair(x, y);
  34.         }
  35.         for(int i=1; i<=n; i++){
  36.             for(int j=1; j<=n; j++){
  37.                 mask = 0;
  38.                 for(int m=1; m<=n; m++){
  39.                     int t1 = (pt[j].first-pt[i].first)*(pt[m].second-pt[i].second);
  40.                     int t2 = (pt[j].second-pt[i].second)*(pt[m].first-pt[i].first);
  41.                     if(t1 == t2) mask |= (1<<(m-1));
  42.                 }
  43.                 mat[i][j] = mask;
  44.             }
  45.         }
  46.         fill(mn, mn+(1<<n), -1);
  47.         target = (1<<n)-1;
  48.         if(n == 1) printf("Case %d: %d\n", k, 1);
  49.         else printf("Case %d: %d\n", k, calc(0));
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 3724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NrFCLK
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!