Pagini recente » Cod sursa (job #2114172) | Cod sursa (job #1882757) | Cod sursa (job #2156300)
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{
double x,y;
};
bool cmp(punct a,punct b){
if(a.x<b.x)
return true;
if(a.x==b.x)
if(a.y<b.y)
return true;
return false;
}
bool semnarie(punct p1,punct p2,punct p3){
return (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y - p1.x*p2.y - p2.x*p3.y -p3.x*p1.y)<0;
}
punct v[120005];
punct stiva [120005];
punct vectorsol[120005];
int main()
{
FILE*fin,*fout;
int n,i;
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w'");
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
sort(v,v+n,cmp);
int vf=0;
stiva[++vf]=v[0];
for(i=1;i<n;i++){
while(vf>1 && !semnarie(stiva[vf-1],stiva[vf],v[i]))
vf--;
stiva[++vf]=v[i];
}
int cvf=vf;
for(i=1;i<=vf;i++){
vectorsol[i]=stiva[i];
}
vf=0;
stiva[++vf]=v[n-1];
for(i=n-2;i>=0;i--){
while(vf>1 && !semnarie(stiva[vf-1],stiva[vf],v[i]))
vf--;
stiva[++vf]=v[i];
}
for(i=2;i<=vf;i++){
vectorsol[i+cvf-1]=stiva[i];
}
cvf+=vf;
cvf-=2;
fprintf(fout,"%d\n",cvf);
for(i=1;i<=cvf;i++)
fprintf(fout,"%lf %lf\n",vectorsol[i].x,vectorsol[i].y);
return 0;
}