Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- ifstream in("infasuratoare.in");
- ofstream out("infasuratoare.out");
- struct point {
- int x, y;
- void read() {
- cin >> x >> y;
- }
- void write() {
- cout << x << ' ' << y << '\n';
- }
- point operator - (const point &B) const {
- return point{x - B.x, y - B.y};
- }
- void operator -= (const point &B) {
- x -= B.x;
- y -= B.y;
- }
- int operator * (const point &B) const {
- return x * B.y - y * B.x;
- }
- int orientation(const point &A, const point &B) const {
- return (A - *this) * (B - *this);
- }
- int dist(point A) {
- A -= *this;
- return A.x * A.x + A.y * A.y;
- }
- bool operator <(const point &A) {
- if(x == A.x) {
- return y < A.y;
- }
- return x < A.x;
- }
- };
- vector<point> upperHull, lowerHull;
- void add(bool upper, vector<point> &hull, point p) {
- while(hull.size() >= 2) {
- int sz = hull.size();
- point P1 = hull[sz - 2];
- point P2 = hull[sz - 1];
- int dir = P1.orientation(P2, p);
- if(dir == 0 || (dir < 0) == upper ) {
- break;
- }
- hull.pop_back();
- }
- hull.push_back(p);
- }
- int32_t main() {
- int n;
- cin >> n;
- vector<point> points(n);
- for(int i = 0; i < n; ++i) {
- points[i].read();
- }
- sort(points.begin(), points.end());
- for(int i = 0; i < n; ++i) {
- add(true, upperHull, points[i]);
- add(false, lowerHull, points[i]);
- }
- upperHull.pop_back();
- lowerHull.erase(lowerHull.begin());
- reverse(lowerHull.begin(), lowerHull.end());
- cout << upperHull.size() + lowerHull.size() << '\n';
- for(auto it : upperHull) {
- it.write();
- }
- for(auto it : lowerHull) {
- it.write();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment