Pagini recente » Cod sursa (job #2816115) | Cod sursa (job #1991937) | Cod sursa (job #657084) | Cod sursa (job #2042384) | Cod sursa (job #2103747)
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
struct Point {
double x, y;
};
inline int Det (Point a, Point b, Point c) {
double d = (a.x * b.y) + (b.x * c.y) + (c.x * a.y) - (a.y * b.x) - (b.y * c.x) - (c.y * a.x);
if (d < 0.0) {
return -1;
}
if (d > 0.0) {
return 1;
}
return 0;
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
//MODIFICA FISIERELE
ios::sync_with_stdio (false);
cout << fixed << setprecision(12);
int n;
cin >> n;
vector < Point > v (n + 1);
for (int i = 1; i <= n; ++ i) {
cin >> v[i].x >> v[i].y;
}
sort (v.begin() + 1, v.end(), [] (Point a, Point b) -> bool {
if (a.x < b.x) {
return true;
}
if (a.x == b.x and a.y < b.y) {
return true;
}
return false;
});
vector < bool > used(n + 1);
vector < int > stk (2 * n + 2);
int peak = 0;
for (int i = 1; i <= n; ++ i) {
while (peak > 1 and Det(v[stk[peak - 1]], v[stk[peak]], v[i]) >= 0) {
-- peak;
}
stk[++ peak] = i;
}
int last = peak;
for (int i = n; i >= 1; -- i) {
while (peak > last and Det(v[stk[peak - 1]], v[stk[peak]], v[i]) >= 0) {
-- peak;
}
stk[++ peak] = i;
}
for (int i = peak; i >= 1; -- i) {
if (used[i]) {
continue;
}
used[i] = true;
cout << v[stk[i]].x << ' ' << v[stk[i]].y << '\n';
}
}