Pagini recente » Istoria paginii runda/preoni_2018/clasament | Cod sursa (job #2216643) | Cod sursa (job #974780) | Autentificare | Cod sursa (job #1238745)
#include <cstdio>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
};
const double eps = 1.e-14;
Point ll;
int ccw (const Point &A, const Point &B, const Point &C) {
double cp = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
if (fabs (cp) < eps)
return 0;
if (cp >= eps)
return 1;
return -1;
}
double dist (const Point &A, const Point &B) {
return sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
class MyComp {
public :
bool operator () (const Point &A, const Point &B) {
int cp;
double d1, d2;
cp = ccw (ll, A, B);
if (cp == 0) {
d1 = dist (ll, A);
d2 = dist (ll, B);
if (d1 - d2 <= -eps)
return 1;
else return 0;
}
if (cp == -1)
return 0;
return 1;
}
};
const int N = 120000;
Point P [N + 10];
int H [N + 10];
int n;
int main () {
int i, poz, u, cp;
Point aux;
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d", &n);
ll.x = ll.y = 1000000000;
for (i = 0; i < n; i ++) {
scanf ("%lf%lf", &P [i].x, &P [i].y);
if (P [i].y - ll.y <= -eps || (fabs (P [i].y - ll.y) < eps && P [i].x - ll.x <= -eps)) {
ll = P [i];
poz = i;
}
}
aux = P [0];
P [0] = P [poz];
P [poz] = aux;
sort (P + 1, P + n, MyComp ());
P [n] = P [0];
H [1] = 0;
H [2] = 1;
i = 2;
u = 2;
while (i <= n) {
cp = ccw (P [H [u - 1]], P [H [u]], P [i]);
if (cp > 0) {
H [++ u] = i;
++ i;
}
else u --;
}
u--;
printf ("%d\n", u);
for (i = 1; i <= u; i ++)
printf ("%.6lf %.6lf\n", P [H [i]].x, P [H [i]].y);
return 0;
}