Pagini recente » Cod sursa (job #448763) | Cod sursa (job #74700) | Cod sursa (job #2781038) | Cod sursa (job #1805055) | Cod sursa (job #302240)
Cod sursa(job #302240)
#include <stdio.h>
#include <algorithm>
#define INf 1000000001
using namespace std;
struct point{double x,y;}P,aux,a[120005],Q[120005];
inline double isLeft(point P1, point P2,point P){
return (P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}
int comp(point x,point y){
return (isLeft(x,y,P)>0);
}
int main(){
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
int i,j,k,l,m,n,LD,q;
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%lf %lf",&a[i].x,&a[i].y);
P.x=INf; P.y=INf;
for (i=1;i<=n;++i)
if (a[i].x < P.x || (a[i].x==P.x && a[i].y<P.y)){
P.x=a[i].x; P.y=a[i].y; LD=i;
}
aux=a[LD]; a[LD]=a[n]; a[n]=aux;
sort(a+1,a+n,comp);
Q[1]=P;
Q[2]=a[1];
q=2;
for (i=2;i<=n;++i){
while ( isLeft(Q[q-1],a[i],Q[q]) > 0)q--;
Q[++q]=a[i];
}
printf("%d\n",q-1);
for (i=2;i<=q;++i)
printf("%lf %lf\n",Q[i].x,Q[i].y);
return 0;
}