Pagini recente » Cod sursa (job #3219013) | Cod sursa (job #3215822) | Cod sursa (job #3231069) | oji_go_10_2 | Cod sursa (job #3295774)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
const int MAX_N = 120000;
int n;
struct Point {
double x, y;
} a[MAX_N + 1];
bool in[MAX_N + 1];
int stk[MAX_N + 1], sz;
double det(Point p1, Point p2, Point p3) {
return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y
- p2.y * p3.x - p3.y * p1.x - p1.y * p2.x;
}
void solve() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
std::sort(a + 1, a + n + 1, [](const Point & a, const Point & b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
});
stk[++sz] = 1;
stk[++sz] = 2;
in[2] = true;
for (int i = 3; i <= n; i++) {
while (sz >= 2 && det(a[i], a[stk[sz - 1]], a[stk[sz]]) >= 0) {
in[stk[sz]] = false;
sz--;
}
stk[++sz] = i;
in[i] = true;
}
for (int i = n; i >= 1; i--) {
if (in[i]) continue;
while (sz >= 2 && det(a[i], a[stk[sz - 1]], a[stk[sz]]) >= 0) {
in[stk[sz]] = false;
sz--;
}
stk[++sz] = i;
in[i] = true;
}
sz--;
fout << sz << '\n';
fout << std::fixed << std::setprecision(12);
for (int i = sz; i >= 1; i--) {
fout << a[stk[i]].x << ' ' << a[stk[i]].y << '\n';
}
}
int main() {
solve();
return 0;
}