Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- typedef long long ll;
- #define all(x) (x).begin(), (x).end()
- using namespace std;
- struct pt {
- ll x, y;
- pt() {
- x = 0; y = 0;
- }
- pt(int _x, int _y) {
- x = _x; y = _y;
- }
- };
- struct vec {
- ll x, y;
- vec(pt p1, pt p2) {
- x = p2.x - p1.x;
- y = p2.y - p1.y;
- }
- };
- ll sign(ll c) {
- if (c == 0) {
- return c;
- } else {
- return c / abs(c);
- }
- }
- ostream& operator<<(ostream& out, pt &p) {
- out << p.x << " " << p.y;
- return out;
- }
- bool operator==(pt p1, pt p2) {
- return p1.x == p2.x && p1.y == p2.y;
- }
- int operator%(vec v1, vec v2) {
- return sign(v1.x * v2.y - v1.y * v2.x);
- }
- lb angle(pt p) {
- return atan2(p.y, p.x);
- }
- bool comp(pt p1, pt p2) {
- ll c = vec(p1, pt()) % vec(p2, pt());
- if (c == 0) {
- return p1.x * p1.x + p1.y * p1.y < p2.x * p2.x + p2.y * p2.y;
- } else {
- return c > 0;
- }
- }
- int main() {
- int n;
- cin >> n;
- vector<pt> pts(n);
- pt mini(1e9 + 1, 1e9 + 1);
- for (int i = 0; i < n; ++i) {
- cin >> pts[i].x >> pts[i].y;
- if (pts[i].y < mini.y || (pts[i].y == mini.y && pts[i].x < mini.x)) {
- mini = pts[i];
- }
- }
- sort(all(pts), comp);
- vector<pt> ans;
- ans.push_back(mini);
- for (int i = 0; i < n; ++i) {
- if (pts[i] == ans.back() || pts[i] == mini) continue;
- while (ans.size() >= 2 && vec(ans[ans.size() - 1], ans[ans.size() - 2]) % vec(ans[ans.size() - 1], pts[i]) >= 0) {
- ans.pop_back();
- }
- ans.push_back(pts[i]);
- }
- n = ans.size();
- cout << n << '\n';
- for (int i = 0; i < n; ++i) {
- cout << ans[i].x << " " << ans[i].y << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement