Pagini recente » Cod sursa (job #1644781) | Cod sursa (job #2237913) | Cod sursa (job #2552595) | Cod sursa (job #2860281) | Cod sursa (job #2562245)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define NMAX 120000
using namespace std;
const double INF = 200000000000;
struct point {
double x, y;
} p[NMAX + 5];
int n, vf;
point st[NMAX + 5];
double panta(point p1, point p2) {
if(p1.x == p2.y) {
if(p1.y < p2.y)
return INF;
return -INF;
}
return (p2.y - p1.y) / (p2.x - p1.x);
}
bool cmp(point p1, point p2) {
double m1 = panta(p[1], p1), m2 = panta(p[1], p2);
if(m1 != m2)
return m1 < m2;
if(m1 < 0)
return p1.x < p2.x;
return p1.x > p2.x;
}
double det(point p1, point p2) {
return p1.x * p2.y - p1.y * p2.x;
}
double cross_product(point p1, point p2, point p3) {
return det(p2, p3) - det(p1, p3) + det(p1, p2);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int pozmin;
double minx = INF;
scanf("%d ", &n);
for(int i = 1; i <= n; i++) {
scanf("%lf %lf ", &p[i].x, &p[i].y);
if(p[i].x < minx) {
minx = p[i].x;
pozmin = i;
}
}
if(pozmin > 1)
swap(p[pozmin], p[1]);
sort(p + 2, p + n + 1, cmp);
vf = 0;
st[++vf] = p[1];
for(int i = 2; i <= n; i++) {
while(vf > 1 && cross_product(st[vf - 1], st[vf], p[i]) < 0)
vf--;
st[++vf] = p[i];
}
printf("%d\n", vf);
for(int i = 1; i <= vf; i++)
printf("%f %f\n", st[i].x, st[i].y);
return 0;
}