ec1117

Untitled

Feb 18th, 2023
267
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.91 KB | None | 0 0
  1. // Problem: B. Forest protection
  2. // Contest: Codeforces - 2018 Southern Russia Open Championship – XII SFU Olympiad «ContestSFedU-2018». Team Final.
  3. // URL: https://codeforces.com/group/j7YsoIFtw4/contest/101790/problem/B
  4. // Memory Limit: 256 MB
  5. // Time Limit: 2000 ms
  6.  
  7. #include <bits/stdc++.h>  
  8. using namespace std;
  9.  
  10. template<typename T>ostream&operator<<(ostream&out,const vector<T>&vec){if(vec.empty()){out<<"[]";return out;}out<<'[';for(int i=0;i<(int)vec.size()-1;i++){out<<vec[i]<<", ";}return out<<vec.back()<<']';}
  11. template<typename T>ostream&operator<<(ostream&out,const set<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
  12. template<typename T>ostream&operator<<(ostream&out,const unordered_set<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
  13. template<typename T>ostream&operator<<(ostream&out,const multiset<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
  14. template<typename T>ostream&operator<<(ostream&out,const unordered_multiset<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
  15. template<typename T1,typename T2>ostream&operator<<(ostream&out,const pair<T1,T2>&pair){return out<<'('<<pair.first<<", "<<pair.second<<')';}
  16.  
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef vector<int> vi;
  20. typedef vector<vector<int>> vvi;
  21. typedef vector<ll> vl;
  22. typedef vector<vector<ll>> vvl;
  23. #define pb push_back
  24. #define endl "\n"
  25.  
  26. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  27. #define all(x) begin(x), end(x)
  28. #define sz(x) (int)(x).size()
  29. typedef long long ll;
  30. typedef pair<int, int> pii;
  31. typedef vector<int> vi;
  32.  
  33.  
  34. template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
  35. template<class T>
  36. struct Point {
  37. typedef Point P;
  38. T x, y;
  39. explicit Point(T x=0, T y=0) : x(x), y(y) {}
  40. bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
  41. bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
  42. P operator+(P p) const { return P(x+p.x, y+p.y); }
  43. P operator-(P p) const { return P(x-p.x, y-p.y); }
  44. P operator*(T d) const { return P(x*d, y*d); }
  45. P operator/(T d) const { return P(x/d, y/d); }
  46. T dot(P p) const { return x*p.x + y*p.y; }
  47. T cross(P p) const { return x*p.y - y*p.x; }
  48. T cross(P a, P b) const { return (a-*this).cross(b-*this); }
  49. T dist2() const { return x*x + y*y; }
  50. double dist() const { return sqrt((double)dist2()); }
  51. // angle to x−axis in interva l [−pi , pi ]
  52. double angle() const { return atan2(y, x); }
  53. P unit() const { return *this/dist(); } // makes d is t ()=1
  54. P perp() const { return P(-y, x); } // rotates +90 degrees
  55. P normal() const { return perp().unit(); }
  56. // returns point rotated ’a ’ radians ccw around the origin
  57. P rotate(double a) const {
  58. return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
  59. friend ostream& operator<<(ostream& os, P p) {
  60. return os << "(" << p.x << "," << p.y << ")"; }
  61. };
  62.  
  63. typedef Point<ll> P;
  64. vector<P> convexHull(vector<P> pts) {
  65. if (sz(pts) <= 1) return pts;
  66. sort(all(pts));
  67. vector<P> h(sz(pts)+1);
  68. int s = 0, t = 0;
  69. for (int it = 2; it--; s = --t, reverse(all(pts)))
  70. for (P p : pts) {
  71. while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
  72. h[t++] = p;
  73. }
  74. return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
  75. }
  76.  
  77.  
  78. array<P, 2> hullDiameter(vector<P> S) {
  79. int n = sz(S), j = n < 2 ? 0 : 1;
  80. pair<ll, array<P, 2>> res({0, {S[0], S[0]}});
  81. rep(i,0,j)
  82. for (;; j = (j + 1) % n) {
  83. res = max(res, {(S[i] - S[j]).dist2(), {S[i], S[j]}});
  84. if ((S[(j + 1) % n] - S[j]).cross(S[i + 1] - S[i]) >= 0)
  85. break;
  86. }
  87. return res.second;
  88. }
  89.  
  90.  
  91. struct pt {
  92.     ll x, y;
  93.     pt(ll x=0, ll y=0) : x(x), y(y) {}
  94. };
  95.  
  96. int orientation(pt a, pt b, pt c) {
  97.     double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
  98.     if (v < 0) return -1; // clockwise
  99.     if (v > 0) return +1; // counter-clockwise
  100.     return 0;
  101. }
  102.  
  103. bool cw(pt a, pt b, pt c, bool include_collinear) {
  104.     int o = orientation(a, b, c);
  105.     return o < 0 || (include_collinear && o == 0);
  106. }
  107. bool ccw(pt a, pt b, pt c, bool include_collinear) {
  108.     int o = orientation(a, b, c);
  109.     return o > 0 || (include_collinear && o == 0);
  110. }
  111.  
  112. void convex_hull(vector<pt>& a, bool include_collinear = false) {
  113.     if (a.size() == 1)
  114.         return;
  115.  
  116.     sort(a.begin(), a.end(), [](pt a, pt b) {
  117.         return make_pair(a.x, a.y) < make_pair(b.x, b.y);
  118.     });
  119.     pt p1 = a[0], p2 = a.back();
  120.     vector<pt> up, down;
  121.     up.push_back(p1);
  122.     down.push_back(p1);
  123.     for (int i = 1; i < (int)a.size(); i++) {
  124.         if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
  125.             while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
  126.                 up.pop_back();
  127.             up.push_back(a[i]);
  128.         }
  129.         if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
  130.             while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
  131.                 down.pop_back();
  132.             down.push_back(a[i]);
  133.         }
  134.     }
  135.  
  136.     if (include_collinear && up.size() == a.size()) {
  137.         reverse(a.begin(), a.end());
  138.         return;
  139.     }
  140.     a.clear();
  141.     for (int i = 0; i < (int)up.size(); i++)
  142.         a.push_back(up[i]);
  143.     for (int i = down.size() - 2; i > 0; i--)
  144.         a.push_back(down[i]);
  145. }
  146.  
  147.  
  148. ll ori(Point<ll> a, Point<ll>b, Point<ll>c) {
  149.     ll v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
  150.     if (v < 0) return -1; // clockwise
  151.     if (v > 0) return +1; // counter-clockwise
  152.     return 0;
  153. }
  154.  
  155. void solve() {
  156.     ll n;
  157.     cin >> n;
  158.    
  159.     vector<Point<ll>> pts(n);
  160.     vector<pt> pts2(n);
  161.     for(int i = 0; i < n; i++) {
  162.         ll x,y;
  163.         cin >> x >> y;
  164.         pts[i] = Point<ll>(x,y);
  165.         pts2[i] = pt(x,y);
  166.     }
  167.     bool suc = false;
  168.     for(int i = 1; i < n; i++) {
  169.         if (ori(pts[i], pts[i-1], pts[0]) == 0) {
  170.             continue;  
  171.         } else {
  172.             suc = true;
  173.             break;
  174.         }
  175.     }
  176.    
  177.     if(!suc) {
  178.         cout << n << endl;
  179.         return;
  180.     }
  181.    
  182.     // cout << pts << endl;
  183.    
  184.    
  185.    
  186.     vector<Point<ll>> hull2 = convexHull(pts);
  187.    
  188.     if ((int) hull2.size() == 3) {
  189.         cout << 2 << endl;
  190.         return;
  191.     }
  192.    
  193.    
  194.     convex_hull(pts2, true);   
  195.     vector<pt> hull_col = pts2;
  196.     vector<Point<ll>> hull (hull_col.size());
  197.     for(int i = 0; i < (int) hull_col.size(); i++) {
  198.         hull[i] = Point<ll>(hull_col[i].x, hull_col[i].y);
  199.     }
  200.    
  201.     // cout << hull << endl;
  202.    
  203.     array<P, 2> diam = hullDiameter(hull2);
  204.    
  205.  
  206.    
  207.     // cout << diam[0] << " " << diam[1] << endl;
  208.     Point<ll> p1 = diam[0];
  209.     Point<ll> p2 = diam[1];
  210.    
  211.    
  212.     int ind1 = -1;
  213.     int ind2 = -1;
  214.     for(int i = 0; i < (int) hull.size(); i++) {
  215.         if(hull[i] == p1) {
  216.             ind1 = i;
  217.         } else if(hull[i] == p2) {
  218.             ind2 = i;
  219.         }
  220.        
  221.     }
  222.    
  223.     int hind1 = -1;
  224.     int hind2 = -1;
  225.     for(int i = 0; i < (int) hull2.size(); i++) {
  226.         if(hull2[i] == p1) {
  227.             hind1 = i;
  228.         } else if(hull2[i] == p2) {
  229.             hind2 = i;
  230.         }
  231.        
  232.     }
  233.  
  234.     // cout << p1 << " " << p2 << endl;
  235. //  
  236.     // cout << hull << endl;
  237.     // cout << hull2 << endl;
  238.     // cout << ind1 << " " << ind2 << endl;
  239.     // cout << hind1 << " " << hind2 << endl;
  240.  
  241.     ll dist = max(ind1, ind2) - min(ind1, ind2) + 1;
  242.     ll other_dist = hull.size() - dist + 2;
  243.     ll sol = min(dist, other_dist);
  244.    
  245.     // cout << dist << " " << other_dist << endl;
  246.    
  247.     // collinear edges
  248.     // if((min(hind1,hind2) + 1 == max(hind1,hind2)) || (min(hind1,hind2) == 0 && max(hind1,hind2) == (int) hull2.size()) {
  249. //     
  250.     // }
  251.    
  252.    
  253.    
  254.    
  255.     // cout << hull << endl;
  256. //  
  257.     // cout << dist << " " << other_dist << endl;
  258.    
  259.     cout << sol << endl;
  260.    
  261.     // ll ans = max(ind1,ind2) - min(ind2,ind1);
  262. }
  263.  
  264.    
  265. int main() {
  266.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
  267.     int tc = 1;
  268.     // cin >> tc;
  269.     for (int t = 1; t <= tc; t++) {
  270.         solve();
  271.     }
  272.     return 0;
  273. }
  274.  
Add Comment
Please, Sign In to add comment