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.
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.
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).
5 3 1 0 4 5 1 2 3 5 2
5 1 5 2 2 3 0 4 3 1
Jedan jednostavan način da se od zadatog skupa tačaka napravi prost mnogougao je da se izabere jedna ekstremna tačka, a zatim da se sve ostale tačke obiđu po redosledu njihovog ugla u odnosu na tu tačku. U ovom rešenju bira se najdesnija tačka, a ako ih ima više sa istom \(x\) koordinatom, bira se ona sa najmanjom \(y\) koordinatom.
Za poređenje uglova nije potrebno računati trigonometrijske funkcije. Dovoljno je posmatrati orijentaciju trojke tačaka \((p_0, A, B)\). Ako je orijentacija pozitivna, tačka \(A\) treba da dođe pre tačke \(B\); ako je negativna, redosled je obrnut. Kada su dve tačke kolinearne sa \(p_0\), one imaju isti ugao, pa ih sortiramo po rastućem rastojanju od \(p_0\). Pošto se porede samo rastojanja, dovoljno je koristiti kvadrat rastojanja, čime se izbegava računanje korena.
Posebno treba obratiti pažnju na poslednju grupu tačaka koje su kolinearne sa \(p_0\). Ako bi one ostale poređane od bliže ka daljoj, završna stranica mnogougla od najudaljenije tačke nazad do \(p_0\) prošla bi kroz bliže tačke iz iste grupe. Zato se ta poslednja kolinearna grupa obrće, tako da se završna stranica povlači od najbliže tačke ka \(p_0\). Time dobijeni redosled predstavlja prost mnogougao čiji je skup temena upravo zadati skup tačaka.
Najskuplji deo algoritma je sortiranje tačaka po uglu, pa je ukupna vremenska složenost \(O(n \log n)\). Pored niza tačaka, koristi se samo konstantan broj pomoćnih promenljivih, pa je dodatna memorijska složenost \(O(1)\).
#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)
{
// Traženje ekstremne tačke. Bira se tačka
// sa najmanjom x koordinatom, a u slučaju
// više takvih, tačka sa najvećom y koordinatom.
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);
}
);
// Menjamo mesta prve i ekstremne tačke.
// Pošto max_element vraća iterator, potrebno
// je dereferenciranje rezultata.
swap(*begin(points), *max);
const Point& p0 = points[0];
// Sortiramo tačke po uglu koji zaklapaju sa tačkom p0 u
// odnosu na y osu. Ne računamo zaista ugao, već
// koristimo orijentaciju tačaka. U slučaju da
// tačke imaju isti ugao, prvo ide ona koja je bliža p0.
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);
}
);
// Ukoliko na kraju postoji grupacija tačaka kolinearnih
// sa p0, potrebno je da obrnemo redosled tih tačaka
// kako bismo ispravno zatvorili mnogougao.
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;
}