Pagini recente » Cod sursa (job #1604732) | Cod sursa (job #2112138) | Cod sursa (job #2676799) | Cod sursa (job #1145872) | Cod sursa (job #1708715)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 120005
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point {
double x, y;
}a[NMAX], st[NMAX];
int N, indexMin = 1, top;
double crossedProduct(point A, point B, point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
void convexHull() {
top = 2;
st[1] = a[1];
st[2] = a[2];
for (int i = 3; i <= N; ++i) {
while (top > 1 && crossedProduct(st[top - 1], st[top], a[i]) > 0) {
--top;
}
st[++top] = a[i];
}
}
int cmp(const point &A, const point &B) {
return crossedProduct(a[1], A, B) < 0;
}
int main() {
f >> N;
for (int i = 1; i <= N; ++i) {
f >> a[i].x >> a[i].y;
if (a[i].x < a[indexMin].x) {
indexMin = i;
} else if (a[i].x == a[indexMin].x && a[i].y < a[indexMin].y) {
indexMin = i;
}
}
swap(a[1], a[indexMin]);
sort(a + 2, a + N + 1, cmp);
convexHull();
g << top << '\n';
g << fixed << setprecision(7);
for (int i = top; i; --i) {
g << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}