Pagini recente » Cod sursa (job #2640314) | Cod sursa (job #1736456) | Cod sursa (job #1229320) | Cod sursa (job #1716589) | Cod sursa (job #1595785)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <utility>
#include <stack>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
#define DIM 120005
struct punct {
double x, y;
} V[DIM], pct;
punct MySt[DIM];
int vf;
int N;
double CrossProduct(punct a, punct b, punct c);
bool cmp(punct a, punct b);
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n", &N);
int pos;
pct.x = 2e9;
pct.y = 2e9;
for(int i = 1; i <= N; ++i) {
scanf("%lf %lf\n", &V[i].x, &V[i].y);
if(pct.y > V[i].y) {
pct = V[i];
pos = i;
}
else {
if(pct.y == V[i].y && pct.x > V[i].x) {
pct = V[i];
pos = i;
}
}
}
swap(V[1], V[pos]);
sort(V + 2, V + 1 + N, cmp);
MySt[vf++] = V[1];
MySt[vf] = V[2];
for(int i = 3; i <= N; ++i) {
while(vf >= 1 && CrossProduct(MySt[vf - 1], MySt[vf], V[i]) > 0) {
--vf;
}
MySt[++vf] = V[i];
}
cout << vf + 1 << '\n';
while(vf >= 0) {
cout << setprecision(9) << fixed << MySt[vf].x << ' ' << MySt[vf].y << '\n';
--vf;
}
return 0;
}
double CrossProduct(punct a, punct b, punct c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(punct a, punct b) {
return (CrossProduct(V[1], a, b) < 0);
}