Pagini recente » Cod sursa (job #1419986) | preOJI 2004 | Profil stay_awake77 | Istoria paginii preoni-2008/runda-1/10 | Cod sursa (job #2070914)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;
struct point{
double x,y;
};
int N,K,st[120100]; point a[120100];
double area(point A, point B, point C){
return (A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x);
}
double sdist(point A, point B){
return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
inline bool cmp(point A, point B){
return (area(a[1],A,B)==0 ? sdist(a[1],A)<sdist(a[1],B) : area(a[1],A,B)>0);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
int i,ind=1;
for (i=1; i<=N; i++){
scanf("%lf %lf",&a[i].x,&a[i].y);
if (a[i].x<a[ind].x) ind=i;
}
swap(a[1],a[ind]);
sort(a+2,a+N+1,cmp);
a[N+1]=a[1];
K=1,st[1]=1;
for (i=2; i<=N; i++){
st[++K]=i;
while (area(a[st[K-1]],a[st[K]],a[i+1])<0) K--;
}
printf("%d\n",K);
for (i=1; i<=K; i++)
printf("%.9lf %.9lf\n", a[st[i]].x, a[st[i]].y);
return 0;
}