SHARE
TWEET

E - Double Fence

a guest Aug 23rd, 2017 186 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define fi first
  6. #define se second
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. struct point{
  13.     ll x, y;
  14.     point() {}
  15.     point(ll a, ll b) {
  16.         x = a;
  17.         y = b;
  18.     }
  19.  
  20.     point operator-(point &p) {
  21.         return point(x - p.x, y - p.y);
  22.     }
  23.  
  24.     ll operator^(const point &p) const {
  25.         return x*p.y - y*p.x;
  26.     }
  27.  
  28.     bool operator<(const point &p) const {
  29.         return (x==p.x) ? (y < p.y) : (x < p.x);
  30.     }
  31.  
  32.     bool operator==(const point &p) const {
  33.         return x == p.x and y == p.y;
  34.     }
  35. };
  36.  
  37. vector<point> convex_hull(vector<point> v) {
  38.     sort(v.begin(), v.end());
  39.     vector<point> up;
  40.     vector<point> lo;
  41.     up.pb(v[0]);
  42.     for(int i = 1; i < v.size(); i++) {
  43.         while(up.size() > 1 and ((up.back() - up[up.size() - 2])^(v[i] - up.back())) > 0LL) {
  44.             up.pop_back();
  45.         }
  46.         up.pb(v[i]);
  47.     }
  48.  
  49.     lo.pb(v.back());
  50.     for(int i = int(v.size()) - 2; i >= 0; i--) {
  51.         while(lo.size() > 1 and ((lo.back() - lo[lo.size() - 2])^(v[i] - lo.back())) > 0LL) {
  52.             lo.pop_back();
  53.         }
  54.         lo.pb(v[i]);
  55.     }
  56.    
  57.     for(int i = 1; i < int(lo.size()) - 1; i++) {
  58.         up.pb(lo[i]);
  59.     }
  60.     return up;
  61. }
  62.  
  63. vector<point> p1, p2;
  64. vector<point> allp;
  65.  
  66. int main(int argc, char* argv[]) {
  67.     int n, m;
  68.     cin >> n >> m;
  69.     for(int i = 0; i < n; i++) {
  70.         int x, y;
  71.         cin >> x >> y;
  72.         p1.pb(point(x, y));
  73.         allp.pb(point(x, y));
  74.     }
  75.  
  76.     for(int i = 0; i < m; i++) {
  77.         int x, y;
  78.         cin >> x >> y;
  79.         p2.pb(point(x, y));
  80.         allp.pb(point(x, y));
  81.     }
  82.  
  83.     sort(p1.begin(), p1.end());
  84.     sort(p2.begin(), p2.end());
  85.     vector<point> ch = convex_hull(allp);
  86.     sort(ch.begin(), ch.end());
  87.  
  88.     cout << ((ch == p1 or ch == p2) ? "YES" : "NO") << endl;
  89.  
  90.     return 0;
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top