Pagini recente » Cod sursa (job #1330528) | Cod sursa (job #804907) | Cod sursa (job #171492) | Cod sursa (job #658514) | Cod sursa (job #2103754)
#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;
}
int index = 0;
vector < int > sol (n + 1);
for (int i = peak; i >= 1; -- i) {
if (used[stk[i]]) {
continue;
}
used[stk[i]] = true;
sol[++ index] = stk[i];
}
cout << index << '\n';
for (int i = 1; i <= index; ++ i) {
cout << v[sol[i]].x << ' ' << v[sol[i]].y << '\n';
}
}