• API
• FAQ
• Tools
• Archive
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.
Top