Pagini recente » Cod sursa (job #887997) | Cod sursa (job #217556) | Cod sursa (job #412561) | Cod sursa (job #39022) | Cod sursa (job #239405)
Cod sursa(job #239405)
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct punct{
double x,y;
};
const int NMAX=120021;
punct a[NMAX],O;
int N,M,s[NMAX];
double prod_vec(punct O,punct A,punct B){
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
int cmp(punct A,punct B){
return prod_vec(O,A,B)>0;
}
int main(){
int i,j;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
scanf("%lf %lf",&a[1].x,&a[1].y);
O=a[1];j=1;
for (i=2;i<=N;++i){
scanf("%lf %lf",&a[i].x,&a[i].y);
if (a[i].y<O.y || (a[i].y==O.y && a[i].x<O.x))
O=a[i],j=i;}
punct aux=a[1];a[1]=a[j];a[j]=aux;
sort(a+2,a+N+1,cmp);
M=2;s[1]=1;s[2]=2;
for (i=3;i<=N;++i){
while (M>=2 && prod_vec(a[s[M]],a[i],a[s[M-1]])<=0) M--;
s[++M]=i;
}
if (prod_vec(a[s[M]],O,a[s[M-1]])==0) --M;
printf("%d\n",M);
for (i=1;i<=M;++i)
printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);
return 0;
}