SHARE
TWEET

Lions, nnoi

Botvan Jan 22nd, 2020 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define all(v) v.begin(), v.end()
  5. #define sz(v) (int)v.size()
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9. using namespace __gnu_cxx;
  10. using ll = long long;
  11. using ld = long double;
  12.  
  13. typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
  14.  
  15. const int L = 1e5 + 1;
  16. const ll MOD = 1e9 + 7;
  17. const ll INF = (1LL << 61);
  18.  
  19. struct point {
  20.     int x, y;
  21.     point(){};
  22.     point(int x, int y) : x(x), y(y){};
  23. };
  24.  
  25. bool cmp(point a, point b) {
  26.     return (a.x < b.x) || (a.x == b.x && a.y < b.y);
  27. }
  28.  
  29. bool cw(point a, point b, point c) {
  30.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
  31. }
  32.  
  33. bool ccw(point a, point b, point c) {
  34.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
  35. }
  36.  
  37. void convex_hull(vector <point> &a) {
  38.     if (sz(a) == 1) return;
  39.     sort(all(a), cmp);
  40.     point p1 = a[0], p2 = a.back();
  41.     vector <point> up, down;
  42.     up.push_back(p1); down.push_back(p1);
  43.     for (int i = 1; i < sz(a); ++i) {
  44.         if (i == sz(a) - 1 || cw(p1, a[i], p2)) {
  45.             while (sz(up) > 1 && !cw(up[sz(up) - 2], up.back(), a[i])) up.pop_back();
  46.             up.push_back(a[i]);
  47.         }
  48.         if (i == sz(a) - 1 || ccw(p1, a[i], p2)) {
  49.             while (sz(down) > 1 && !ccw(down[sz(down) - 2], down.back(), a[i])) down.pop_back();
  50.             down.push_back(a[i]);
  51.         }
  52.     }
  53.     a.clear();
  54.     for (auto i : up) a.push_back(i);
  55.     for (int i = sz(down) - 2; i > 0; --i) a.push_back(down[i]);
  56. }
  57.  
  58. int nex(int x, vector <int> &v) {
  59.     if (x < sz(v) - 1) return x + 1;
  60.     else return 0;
  61. }
  62.  
  63. int pr(int x, vector <int> &v) {
  64.     if (x > 0) return x - 1;
  65.     else return sz(v) - 1;
  66. }
  67.  
  68. bool qq(point a, point b) {return a.x == b.x;}
  69.  
  70. int n;
  71. point a;
  72. vector <point> v;
  73. bool lu, ld, ru, rd;
  74.  
  75. int main() {
  76.     ios_base::sync_with_stdio(0);
  77.     cin.tie(0); cout.tie(0);
  78.  
  79.     cin >> n;
  80.     cin >> a.x >> a.y;
  81.     v.resize(n);
  82.     for (int i = 0; i < n; ++i) {
  83.         int x, y;
  84.         cin >> x >> y;
  85.         if (x < a.x && y < a.y) ld = true;
  86.         else if (x < a.x && y > a.y) lu = true;
  87.         else if (x > a.x && y < a.y) rd = true;
  88.         else if (x > a.x && y > a.y) ru = true;
  89.         v[i] = point(x, y);
  90.     }
  91.     if (lu && ld && ru && rd) {
  92.         cout << "NO";
  93.         exit(0);
  94.     }
  95.     v.push_back(a);
  96.     convex_hull(v);
  97.     if (n == 1) {
  98.         if (qq(a, v[0])) cout << a.x - (v[1].x - a.x) << ' ' << a.y - (v[1].y - a.y);
  99.         else cout << a.x - (v[0].x - a.x) << ' ' << a.y - (v[0].y - a.y);
  100.     }
  101.     else {
  102.         int pos;
  103.         for (int i = 0; i < n; ++i) {
  104.             if (a == v[i]) {
  105.                 pos = i;
  106.                 break;
  107.             }
  108.         }
  109.         point p = v[pr(pos, v)], q = v[nex(pos, v)];
  110.         if (p.x == q.x) {
  111.  
  112.         }
  113.         else {
  114.  
  115.         }
  116.     }
  117.  
  118.     return 0;
  119. }
  120. /// ACTUAL CODE STARTS HERE:
  121. /*
  122.      ▄▀▀▀▄
  123. ▄███▀░◐░░░▌
  124.     ▌░░░░░▐
  125.     ▐░░░░░▐
  126.     ▌░░░░░▐▄▄
  127.     ▌░░░░▄▀▒▒▀▀▀▀▄
  128.    ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
  129.    ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
  130.     ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
  131.       ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
  132.            ▌▌░▌▌
  133.            ▌▌░▌▌
  134.          ▄▄▌▌▄▌▌        */
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