Pagini recente » Cod sursa (job #2123138) | Cod sursa (job #2610992) | Cod sursa (job #1684100) | Cod sursa (job #1656131) | Cod sursa (job #1465157)
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{double x,y;};
punct v[120010],stiva[120010];
int compare(int a,int b){
if(v[a].x<v[b].x)
return a;
if(v[a].x>v[b].x)
return b;
if(v[a].y<=v[b].y)
return a;
return b;
}
void schimba(int a,int b){
punct aux;
aux=v[a];
v[a]=v[b];
v[b]=aux;
}
bool cmp(punct a,punct b){
if((a.x-v[1].x)*(b.y-v[1].y)-(a.y-v[1].y)*(b.x-v[1].x)<0)
return true;
return false;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,k=2;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
for(i=2;i<=n;i++)
if(compare(1,i)==i)
schimba(1,i);
sort(v+2,v+n+1,cmp);
stiva[1]=v[1];
stiva[2]=v[2];
for(i=3;i<=n;i++){
while(k>=2&&(stiva[k].x-stiva[k-1].x)*(v[i].y-stiva[k-1].y)-(stiva[k].y-stiva[k-1].y)*(v[i].x-stiva[k-1].x)>0)
k--;
k++;
stiva[k]=v[i];
}
printf("%d\n",k);
for(i=k;i>=1;i--)
printf("%.9f %.9f\n",stiva[i].x,stiva[i].y);
return 0;
}