Advertisement
vfonic

Untitled

Dec 18th, 2013
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <vector>
  17.  
  18. #define inf 1000000000
  19.  
  20. using namespace std;
  21.  
  22. typedef pair<int, int> point;
  23.  
  24. #define x first
  25. #define y second
  26.  
  27. int ccw(point a, point b, point c) {
  28. return (long long)(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  29. }
  30.  
  31. vector<point> points;
  32. int n;
  33.  
  34. vector<point> envelope(int p) {
  35. vector<point> hull;
  36. hull.push_back(points[0]);
  37. hull.push_back(points[1]);
  38.  
  39. for (int i = 2; i < n; ++i) {
  40. while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), points[i]) * p >= 0) {
  41. hull.pop_back();
  42. }
  43. hull.push_back(points[i]);
  44. }
  45.  
  46. return hull;
  47. }
  48.  
  49. int main() {
  50. scanf("%d", &n);
  51.  
  52. points.resize(n);
  53. for (int i = 0; i < n; ++i) {
  54. scanf("%d%d", &points[i].x, &points[i].y);
  55. }
  56.  
  57. sort(points.begin(), points.end());
  58.  
  59. int sol = 1;
  60. for (; !points.empty(); ++sol) {
  61. vector<point> upper_envelope = envelope(+1);
  62. vector<point> lower_envelope = envelope(-1);
  63.  
  64. // points[0], points[n-1]
  65. // upper & lower_envelope
  66. vector<point> new_points;
  67.  
  68. vector<point>::iterator l_it = lower_envelope.begin();
  69. vector<point>::iterator u_it = upper_envelope.begin() + 1;
  70. for (vector<point>::iterator it = points.begin(); it != points.end(); ++it) {
  71. if (l_it != lower_envelope.end() && *it == *l_it) { ++l_it; continue; }
  72. if (u_it != upper_envelope.end() && *it == *u_it) { ++u_it; continue; }
  73. new_points.push_back(*it);
  74. }
  75.  
  76. points = new_points;
  77. }
  78.  
  79. printf("%d\n", sol);
  80.  
  81. return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement