Advertisement
Guest User

Untitled

a guest
Mar 1st, 2013
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. int convexity_n4(vector<point> a) {
  2.   sort(all(a)); //sort by increasing of x, if equal: by y
  3.  
  4.   int ans = 0;
  5.   forn(i, a.size()) {
  6.     vector<point> b(a.begin() + i + 1, a.end());
  7.     sort(all(b), cmp(a[i])); //sort by relative angle to a[i]
  8.  
  9.     b.insert(b.begin(), a[i]);
  10.  
  11.     if ((int)b.size() <= ans)
  12.       continue;
  13.  
  14.     memset(z, 0, sizeof(z));
  15.     for (int j = 1; j < (int)b.size(); j++) {
  16.       z[0][j] = 2;
  17.       forn(t, j)
  18.         if (z[t][j]) {
  19.           ans = max(ans, z[t][j]);
  20.           for (int k = j + 1; k < (int)b.size(); k++)
  21.             if (vec(b[t], b[j], b[k]) > 0)
  22.               z[j][k] = max(z[j][k], z[t][j] + 1);
  23.         }
  24.     }
  25.   }
  26.  
  27.   return ans;
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement