Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- using namespace std;
- #define all(x) x.begin(), x.end()
- #define endl '\n'
- #define sz(x) (int)(x).size()
- #define mp(x, y) make_pair(x, y)
- #define pb push_back
- #define pii pair<int, int>
- #define rep(i, f, t) for (auto i = (f); i < (t); ++i)
- #define ui unsigned int
- #define ll long long
- #define double long double
- #define ull unsigned long long
- const int inf = (int)(2e9);
- const ll INF = (ll)(1e18);
- const int MOD = (int)(1e9 + 7);
- const double eps = (double)(1e-9);
- const double pi = acos(-1);
- const int maxn = (int)(1e5 + 10);
- const int maxm = (int)(2e5 + 10);
- void solve();
- template <typename A> inline void print(A x) { cout << x << endl; }
- template <typename A, typename B> inline void print(A x, B y) { cout << x << ' ' << y << endl; }
- template <typename A, typename B, typename C> inline void print(A x, B y, C z) { cout << x << ' ' << y << ' ' << z << endl; }
- template <typename A> inline void in(A &x) { cin >> x; }
- template <typename A, typename B> inline void in(A &x, B &y) { cin >> x >> y; }
- template <typename A, typename B, typename C> inline void in(A &x, B &y, C &z) { cin >> x >> y >> z; }
- template <typename A, typename B, typename C, typename D> inline void in(A &x, B &y, C &z, D &p) { cin >> x >> y >> z >> p; }
- template <typename A> inline void read(A begin, A end) { while (begin != end) cin >> *(begin++); }
- template <typename A> inline void write(A begin, A end) { while (begin != end) { cout << *(begin++) << ' '; } cout << endl; }
- ll power(ll a, ll b)
- {
- if (b == 0) return 1;
- if (b & 1) return power(a, b - 1) * a;
- ll tmp = power(a, b / 2);
- return tmp * tmp;
- }
- void use_files(string s) {
- freopen(string(s + ".in").c_str(), "r", stdin);
- freopen(string(s + ".out").c_str(), "w", stdout);
- }
- signed main()
- {
- std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- srand((ui)(time(0)));
- cout << fixed << setprecision(20);
- solve();
- return 0;
- }
- struct point {
- int x;
- int y;
- };
- vector<point> arr;
- bool comp(point& a, point& b)
- {
- return atan2(a.y - arr[0].y, a.x - arr[0].x) < atan2(b.y - arr[0].y, b.x - arr[0].x);
- }
- int cross_product(point& a, point& b, point& c, point& d)
- {
- point x, y;
- x.x = b.x - a.x, x.y = b.y - a.y;
- y.x = d.x - c.x, y.y = d.y - c.y;
- return x.x * y.y - y.x * x.y;
- }
- void solve()
- {
- int n;
- cin >> n;
- arr.resize(n);
- rep(i, 0, n) {
- cin >> arr[i].x >> arr[i].y;
- }
- if (n == 1) {
- print(1);
- print(arr[0].x, arr[0].y);
- return;
- }
- rep(i, 0, n) {
- if (arr[i].x <= arr[0].x && arr[i].y < arr[0].y)
- swap(arr[i], arr[0]);
- }
- sort(arr.begin() + 1, arr.end(), &comp);
- vector<point> ans;
- ans.push_back(arr[0]);
- ans.push_back(arr[1]);
- rep(i, 2, n) {
- while (sz(ans) > 1 && cross_product(ans[sz(ans) - 2], ans[sz(ans) - 1], ans[sz(ans) - 1], arr[i]) <= 0)
- ans.pop_back();
- ans.push_back(arr[i]);
- }
- if (n & 1)
- reverse(all(ans));
- print(sz(ans));
- rep(i, 0, sz(ans))
- print(ans[i].x, ans[i].y);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement