Pagini recente » Cod sursa (job #2591072) | Cod sursa (job #2810237) | Cod sursa (job #2588077) | Cod sursa (job #2641891) | Cod sursa (job #2166575)
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
const int NMax = 120002;
int N, ind;
double minX = 1000000000, minY = 1000000000;
struct point {double x, y;} v[NMax], sol[NMax];
double aria(point A, point B, point C){
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
inline bool cmp(point A, point B){
return (aria(v[1], A, B) > 0);
}
int main(){
scanf("%d", &N);
for (int i = 1; i <= N; i++){
scanf("%lf%lf", &v[i].x, &v[i].y);
if (v[i].y < minY)
ind = i;
else
if (v[i].y == minY && v[i].x < minX)
ind = i;
}
swap(v[1], v[ind]);
sort(v + 2, v + N + 1, cmp);
for (int i = 1; i < 4; i++)
sol[i] = v[i];
int card = 3;
for (int i = 4; i <= N; i++){
while (aria(sol[card - 1], sol[card], v[i]) < 0)
card --;
sol[++ card] = v[i];
}
printf("%d\n", card);
for (int i = 1; i <= card; i++)
printf("%.12f %.12f\n", sol[i].x, sol[i].y);
}