Pagini recente » Cod sursa (job #1982639) | Cod sursa (job #3227732) | Cod sursa (job #1966915) | Cod sursa (job #1076522) | Cod sursa (job #1497097)
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MULT = 2000000000;
const int XMAX = 1000000000;
const int NMAX = 120010;
const double Ep = 0.0000000000001;
struct punct {double x, y;};
punct v[NMAX], minim;
int N;
punct stiva[NMAX];
int h;
double raport (punct a) {
if (a.x == 0) {
if (a.y < 0) {
return -MULT;
}
return MULT;
}
return (a.y - minim.y) / (a.x - minim.x);
}
bool criteriu (punct a, punct b) {
a.x -= minim.x; b.x -= minim.x;
a.y -= minim.y; b.y -= minim.y;
if (abs (raport (a) - raport (b)) < Ep) {
double da = sqrt (a.x * a.x + a.y * a.y);
double db = sqrt (b.x * b.x + b.y + b.y);
return da < db;
}
return raport (a) < raport (b);
}
double determ (punct a, punct b, punct c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d", &N);
minim.x = minim.y = MULT;
for (int i = 1; i <= N; i++) {
scanf ("%lf%lf", &v[i].x, &v[i].y);
if (v[i].x < minim.x) {
minim = v[i];
}
else {
if (v[i].x == minim.x && v[i].y < minim.y) {
minim = v[i];
}
}
}
sort (v + 1, v + N + 1, criteriu);
stiva[1] = minim;
h = 1;
for (int i = 1; i <= N; i++) {
if (v[i].x == minim.x && v[i].y == minim.y) {
continue;
}
while (h > 1 && determ (stiva[h - 1], stiva[h], v[i]) < 0) {
h --;
}
stiva[++h] = v[i];
}
while (h > 1 && determ (stiva[h - 1], stiva[h], stiva[1]) < 0) {
h --;
}
printf ("%d\n", h);
for (int i = 1; i <= h; i++) {
printf ("%f %f\n", stiva[i].x, stiva[i].y);
}
return 0;
}