Pagini recente » Cod sursa (job #3189974) | Cod sursa (job #2962327) | Cod sursa (job #1975036) | Cod sursa (job #1119011) | Cod sursa (job #704947)
Cod sursa(job #704947)
#include <cstdio>
#include <algorithm>
#define NMAX 100050
#define INF 0x3f3f3f3f
using namespace std;
struct punct {
double x, y;
};
int V[NMAX], N, M, pmin;
double xmin, ymin;
punct P[NMAX];
bool cmp (punct, punct), convex (int, int, int);
void infasuratoare (), input (), output ();
int main () {
input ();
infasuratoare ();
output ();
return 0;
}
void infasuratoare () {
swap (P[1], P[pmin]);
sort (P + 2, P + 1 + N, cmp);
M = 2; V[1] = 1, V[2] = 2;
for (int i = 3; i <= N; i++) {
while (M > 2 && !convex (V[M-1], V[M], i)) M--;
V[++M] = i;
}
}
bool cmp (punct a, punct b) {
return a.x * b.y > b.x * a.y;
}
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 r = (x3 - x2) * (y1 - y2) + (x1 - x2) * (y2 - y3);
if (r > 0) return 1;
return 0;
}
void input () {
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &N);
xmin = ymin = INF;
for (int i = 1; i <= N; i++) {
scanf ("%lf %lf", &P[i].x, &P[i].y);
if (P[i].y < ymin)
xmin = P[i].x, ymin = P[i].y, pmin = i;
}
for (int i = 1; i <= N; i++)
P[i].x -= xmin, P[i].y -= ymin;
}
void output () {
freopen ("infasuratoare.out", "w", stdout);
printf ("%d\n", M);
for (int i = 1; i <= M; i++)
printf ("%.6lf %.6lf\n", P[ V[i] ].x + xmin, P[ V[i] ].y + ymin);
}