Advertisement
Malinovsky239

convex hull

Oct 26th, 2011
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. #define N 1005
  7.  
  8. using namespace std;
  9.  
  10. struct vect {
  11.     int x, y;
  12.  
  13.     void read() {
  14.         cin >> x >> y;
  15.     }
  16.  
  17.     void print() {
  18.         cout << x << " " << y << endl;
  19.     }
  20.  
  21.     vect() {}
  22.  
  23.     vect(int a, int b) {
  24.         x = a, y = b;
  25.     }
  26.  
  27.     int sq_length() {
  28.         return x * x + y * y;
  29.     }
  30. };
  31.  
  32. vect operator - (vect a, vect b) {
  33.     return vect(a.x - b.x, a.y - b.y);
  34. }
  35.  
  36. int operator * (vect a, vect b) {
  37.     return a.x * b.y - a.y * b.x;
  38. }
  39.  
  40. int operator ^ (vect a, vect b) {
  41.     return a.x * b.x + a.y * b.y;
  42. }
  43.  
  44. vect start, center, p[N], p2[N], st[N];
  45. int n, top = 0, m;
  46. bool del[N];
  47.  
  48. void push(vect a) {
  49.     st[top++] = a;
  50. }
  51.  
  52. bool comp(vect a, vect b) {
  53.     a = a - start;
  54.     b = b - start;
  55.     if (a * b == 0)
  56.         return a.sq_length() < b.sq_length();      
  57.     return a * b > 0;
  58. }
  59.  
  60. int main() {
  61.     cin >> n;
  62.     center.read();
  63.    
  64.     for (int i = 0; i < n; i++)
  65.         p[i].read();
  66.  
  67.     start = p[0];
  68.     int ind = 0;
  69.     for (int i = 1; i < n; i++)
  70.         if (p[i].y < start.y || (p[i].y == start.y && p[i].x < start.x))
  71.             start = p[i], ind = i;
  72.  
  73.     swap(p[0], p[ind]);
  74.  
  75.     sort(p + 1, p + n, comp);
  76.  
  77.     for (int i = n - 2; i > 0; i--)
  78.         if ( (p[i] - start) * (p[i + 1] - start) == 0 )
  79.             del[i] = true;
  80.  
  81.     for (int i = 0; i < n; i++)
  82.         if (!del[i])
  83.             p2[m++] = p[i];
  84.  
  85.     p2[m++] = p2[0];
  86.  
  87.     for (int i = 0; i < 3; i++)
  88.         push(p2[i]);
  89.  
  90.     for (int i = 3; i < m; i++) {
  91.         while ((p2[i] - st[top - 1]) * (st[top - 1] - st[top - 2]) >= 0)
  92.             top--;
  93.         push(p2[i]);
  94.     }
  95.  
  96.     int answer = 0;
  97.  
  98.     for (int i = 1; i < top; i++) {
  99.         if ( ((center - st[i - 1]) ^ (st[i] - st[i - 1])) > 0 && ((center - st[i]) ^ (st[i - 1] - st[i])) > 0 )    
  100.             answer++;
  101.     }
  102.  
  103.     cout << answer;
  104.  
  105.     return 0;
  106. }
  107.  
  108.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement