Konstrukcija prostog monogougla

Prost mnogougao je mnogougao u kom se nikoje dve stranice ne seku (osim što se susedne stranice dodiruju u zajedničkom temenu). Napiši program koji za dati skup tačaka (u kom nisu sve tačke kolinearne) određuje neki prost mnogougao kom je skup temena jednak tom skupu tačaka.

Opis ulaza

Sa standradnog ulaza se učitava broj \(n\) (\(3 \leq n \leq 50000\)), a zatim i \(n\) tačaka (svaka tačka je opisana u posebnom redu pomoću svoje dve celobrojne koordinate razdvojene razmakom). Sve učitane tačke su različite i nisu sve kolinearne.

Opis izlaza

Na standardni izlaz ispisati permutaciju učitanog niza tačaka koja predstavlja redosled temena konstruisanog prostog mnogougla (tačke treba da budu opisane na isti način kao i na ulazu).

Primer

Ulaz

5
3 1
0 4
5 1
2 3
5 2

Izlaz

5 1
5 2
2 3
0 4
3 1

Rešenje

Opis glavnog rešenja

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Point {
    double x;
    double y;
};

double orientation(const Point &A, const Point &B, const Point &C) 
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

double distance(const Point &A, const Point &B) 
{
    double dx = B.x - A.x;
    double dy = B.y - A.y;

    return dx * dx + dy * dy;
}

void simple_polygon(vector<Point> &points)
{
    auto max = 
        max_element(
            begin(points), end(points),
            [](const Point& p1, const Point& p2) {
                return p1.x < p2.x || (p1.x == p2.x && p1.y > p2.y);
            }
        );

    swap(*begin(points), *max);
    const Point& p0 = points[0];

    sort(
        next(begin(points)), end(points),
        [p0](const Point& p1, const Point& p2) {
            auto o = orientation(p0, p1, p2);
            if (o > 0) {
                return true;
            } else if (o < 0) {
                return false;
            }
            return distance(p0, p1) <= distance(p0, p2);
        }
    );

    auto it = prev(end(points));
    while (orientation(*prev(it), *it, p0) == 0) {
        it = prev(it);
    }
    reverse(it, end(points));
}

int main(void)
{
    int n; cin >> n;

    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }

    simple_polygon(points);

    for (const auto &p : points) {
        cout << p.x << " " << p.y << endl;
    }
    
    return 0;
}