Pagini recente » Cod sursa (job #1408115) | Cod sursa (job #1918035) | Cod sursa (job #1117921) | Cod sursa (job #474228) | Cod sursa (job #475819)
Cod sursa(job #475819)
#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);
}
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;
}