Pagini recente » Cod sursa (job #236904) | Cod sursa (job #435091) | Cod sursa (job #1148633) | Cod sursa (job #2406968) | Cod sursa (job #387613)
Cod sursa(job #387613)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 120010
struct punct {double x, y, ctg;} v[Nmax], aux;
int n, i, pmin;
int S[Nmax];
double xmin, ymin;
void citire (), afisare ();
int cmp (punct a, punct b) {
return a.ctg > b.ctg;
}
int pozitie (double x1, double y1, double x2, double y2, double x3, double y3) {
double A = x1*y2 + x2*y3 + x3*y1 - y2*x3 - y3*x1 - y1*x2;
if (A >= 0) return 1;
return 0;
}
void infasuratoare () {
aux = v[pmin]; v[pmin] = v[1]; v[1] = aux;
v[1].x = v[1].y = 0;
for (i = 2; i <= n; i++) {
v[i].x-= xmin;
v[i].y-= ymin;
v[i].ctg = v[i].x / v[i].y;
}
sort (v + 2, v + n + 1, cmp);
v[n + 1] = v[1];
S[++S[0]] = 1;
for (i = 2; i <= n + 1; i++) {
while (S[0] > 2 && pozitie ( v[ S[S[0]] ].x, v[ S[S[0]] ].y, v[ S[S[0] - 1] ].x, v[ S[S[0] - 1] ].y, v[i].x, v[i].y))
S[0]--;
S[++S[0]] = i;
}
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
citire ();
infasuratoare ();
afisare ();
return 0;
}
void citire () {
scanf ("%d", &n);
scanf ("%lf %lf", &v[1].x, &v[1].y);
xmin = v[1].x; ymin = v[1].y;
for (i = 2; i <= n; i++) {
scanf ("%lf %lf", &v[i].x, &v[i].y);
if (v[i].y < ymin || (v[i].y == ymin && v[i].x < xmin)) {
xmin = v[i].x;
ymin = v[i].y;
pmin = i;
}
}
}
void afisare () {
printf ("%d\n", S[0] - 1);
for (i = 1; i < S[0]; i++)
printf ("%lf %lf\n", v[S[i]].x + xmin, v[S[i]].y + ymin);
}