Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <algorithm>
- #include <memory.h>
- #include <stack>
- #define pb push_back
- #define ll long long
- using namespace std;
- double pi = acos(-1);
- struct point {
- int x, y;
- };
- int cross(const point &a, const point &b, const point &c) {
- return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
- }
- bool cmp(const point &a, const point &b) {
- return (a.x < b.x) || (a.x == b.x && a.y < b.y);
- }
- int main() {
- //freopen("convex.in", "r", stdin);
- //freopen("convex.out", "w", stdout);
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n;
- cin >> n;
- vector <point> s(n);
- for(int i = 0; i < n; ++i)
- cin >> s[i].x >> s[i].y;
- if(n == 1) {
- cout << "1" << endl;
- cout << s[0].x << " " << s[0].y << endl;
- return 0;
- }
- if(n == 2) {
- if(s[0].x == s[1].x && s[0].y == s[0].y) {
- cout << "1" << endl;
- cout << s[1].x << " " << s[1].y << endl;
- return 0;
- }
- }
- sort(s.begin(), s.end(), cmp);
- point p1 = s[0], p2 = s[s.size() - 1];
- vector <point> up, down;
- up.pb(p1);
- down.pb(p1);
- for(int i = 1; i < n - 1; ++i) {
- if(cross(p1, s[i], p2) < 0) {
- while(up.size() >= 2 && cross(up[up.size() - 2], up[up.size() - 1], s[i]) >= 0)
- up.pop_back();
- up.pb(s[i]);
- }
- else if(cross(p1, s[i], p2) > 0) {
- while(down.size() >= 2 && cross(down[down.size() - 2], down[down.size() - 1], s[i]) <= 0)
- down.pop_back();
- down.pb(s[i]);
- }
- }
- while(up.size() > 2 && cross(up[up.size() - 2], up[up.size() - 1], p2) >= 0)
- up.pop_back();
- up.pb(p2);
- while(down.size() > 2 && cross(down[down.size() - 2], down[down.size() - 1], p2) <= 0)
- down.pop_back();
- down.pb(p2);
- cout << down.size() + up.size() - 2 << endl;
- if(n % 2 == 0) {
- for(int i = up.size() - 1; i >= 0; --i)
- cout << up[i].x << " " << up[i].y << endl;
- for(int i = 1; i < down.size() - 1; ++i)
- cout << down[i].x << " " << down[i].y << endl;
- return 0;
- }
- else {
- for(int i = 0; i < up.size(); ++i)
- cout << up[i].x << " " << up[i].y << endl;;
- for(int i = down.size() - 2; i >= 1; --i)
- cout << down[i].x << " " << down[i].y << endl;
- return 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement