Pagini recente » Cod sursa (job #1429291) | Cod sursa (job #849236) | Cod sursa (job #1285047) | Cod sursa (job #2553396) | Cod sursa (job #557521)
Cod sursa(job #557521)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 120050
#define INF 1 << 30
struct punct {
double x, y, ctg;
} P[NMAX];
int S[NMAX], N, n, pmin;
double xmin, ymin;
void citire (), infasuratoare (), afisare ();
int main () {
citire ();
infasuratoare ();
afisare ();
return 0;
}
void citire () {
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &n);
ymin = INF;
for (int i = 1; i <= n; i++) {
scanf ("%lf %lf", &P[i].x, &P[i].y);
if (P[i].y < ymin)
ymin = P[i].y, xmin = P[i].x, pmin = i;
}
}
bool cmp (punct a, punct b) {
return a.ctg > b.ctg;
}
bool convex (int a, int b, int c) {
double X1 = P[a].x, Y1 = P[a].y, X2 = P[b].x, Y2 = P[b].y, X3 = P[c].x, Y3 = P[c].y;
double A = (X1 - X3) * (Y2 - Y3) - (X2 - X3) * (Y1 - Y3);
if (A > 0) return 1;
return 0;
}
void infasuratoare () {
swap (P[1], P[pmin]); P[1].x = P[1].y = 0;
for (int i = 2; i <= n; i++) {
P[i].x -= xmin, P[i].y -= ymin;
P[i].ctg = P[i].x / P[i].y;
}
sort (P + 2, P + 1 + n, cmp);
N = 2, S[1] = 1, S[2] = 2;
for (int i = 3; i <= n; i++) {
while (N >= 2 && !convex (S[N-1], S[N], i))
N--;
S[++N] = i;
}
}
void afisare () {
freopen ("infasuratoare.out", "w", stdout);
printf ("%d\n", N);
for (int i = 1; i <= N; i++)
printf ("%lf %lf\n", P[ S[i] ].x + xmin, P[ S[i] ].y + ymin);
}