Pagini recente » Cod sursa (job #36485) | Cod sursa (job #1418525) | Cod sursa (job #2494289) | Cod sursa (job #2808701) | Cod sursa (job #1238726)
#include <cstdio>
#include <cmath>
#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 = ((double)B.x - A.x) * ((double)C.y - B.y) - ((double)B.y - A.y) * ((double)C.x - B.x);
if (cp < 0)
return -1;
if (cp == 0)
return 0;
return 1;
}
double dist (const Point &A, const Point &B) {
return ((double)A.x - B.x) * ((double)A.x - B.x) + ((double)A.y - B.y) * ((double)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 = 100000;
Point P [N], H [N];
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 ());
u = 0;
H [++ u] = ll;
H [++ u] = P [1];
i = 2;
while (i < n) {
cp = ccw (H [u - 1], H [u], P [i]);
if (cp > 0) {
H [++ u] = P [i];
++ i;
}
else u --;
}
printf ("%d\n", u);
for (i = 1; i <= u; i ++)
printf ("%lf %lf\n", H [i].x, H [i].y);
return 0;
}