Pagini recente » Cod sursa (job #2543435) | Cod sursa (job #496283) | Cod sursa (job #2397000) | Cod sursa (job #1194368) | Cod sursa (job #961402)
Cod sursa(job #961402)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define point pair <double, double>
#define x first
#define y second
using namespace std;
int cntH;
point X[120100], H[120100];
inline int ccw(point A, point B, point C) {
return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}
inline double dist(point A, point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
inline bool comp(point A, point B) {
return ccw(X[1], A, B) > 0 ? 1 : 0;
}
void convexHull(int N) {
int i;
for (i = 1; i <= N; ++i)
if (X[i].y < X[1].y || (X[i].y == X[1].y && X[i].x < X[1].x))
swap(X[1], X[i]);
sort(X + 2, X + N + 1, comp);
X[++N] = X[1];
H[++cntH] = X[1]; H[++cntH] = X[2];
int currentPoint = 3;
while (currentPoint <= N)
if (ccw(H[cntH - 1], H[cntH], X[currentPoint]) > 0) {
H[++cntH] = X[currentPoint];
++currentPoint;
} else
--cntH;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i, N;
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%lf%lf", &X[i].x, &X[i].y);
convexHull(N);
printf("%d\n", cntH - 1);
for (i = 1; i < cntH; ++i)
printf("%lf %lf\n", H[i].x, H[i].y);
return 0;
}