Pagini recente » Cod sursa (job #2544248) | eusebiu_oji_2014_cls10 | Cod sursa (job #15007) | Cod sursa (job #2754337) | Cod sursa (job #475818)
Cod sursa(job #475818)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 120005
struct punct {
double x; double y;
} siri[DN],sol[DN];
int n;
int cmp(punct x, punct y) {
if(x.x<y.x) return 1;
else if(x.x>y.x) return -1;
else return x.y<y.y;
}
int pointLocation(punct x, punct y,punct z) {
int cp1=(y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
return cp1>0;
}
void in() {
int ind=1,fol[DN]={0,0,1},i=3,stiva[DN]={0,1,2},vf=2;
for( ;!fol[1];) {
for( ;fol[i]; i+=ind ) if(i==n) ind=-1;
while(vf>=2 && pointLocation(siri[stiva[vf-1]],siri[stiva[vf]],siri[i])) fol[stiva[vf--]]=0;
stiva[++vf]=i;
fol[i]=1;
}
printf("%d\n",vf-1);
for(i=1; i<vf; ++i) printf("%6lf %6lf\n",siri[stiva[i]].x,siri[stiva[i]].y);
printf("%6lf %6lf\n",siri[stiva[1]].x,siri[stiva[1]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%lf %lf",&siri[i].x,&siri[i].y);
sort(siri+1,siri+n+1,cmp);
in();
return 0;
}