Pagini recente » Cod sursa (job #1149984) | Cod sursa (job #836425) | Cod sursa (job #1469841) | Cod sursa (job #2215649) | Cod sursa (job #876427)
Cod sursa(job #876427)
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<limits.h>
#define dim 120007
using namespace std;
int stiv[dim],srt[dim],n;
double x[dim],y[dim];
int idx,PunctInitial,i;
bool cmpt(int i ,int j) {
return (double)(x[i]-x[PunctInitial])*(y[j]-y[PunctInitial ]) <(double)(x[j]-x[PunctInitial])*(y[i]-y[PunctInitial ]);
}
long double unghi(int a,int b,int c)
{
return (long double)x[a] * y[b] + x[b] * y[c] + x[c] * y[a] - y[a] * x[b] - y[b] * x[c] - y[c] * x[a];
}
int main (){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
x[0]=y[0]=10000000;
PunctInitial=idx=0;
for(i=1;i<=n;i++){
scanf("%lf %lf",&x[i],&y[i]);
if(x[i]<x[idx] || (x[i]==x[idx] && y[i]<y[idx]))
idx=i;
}
PunctInitial=idx;
for(i=1;i<=n;i++){
if(i==PunctInitial)continue;
srt[++srt[0]]=i;
}
sort(srt+1,srt+srt[0]+1,cmpt);
stiv[0]=1;
stiv[1]=PunctInitial;
for(i=1;i<=srt[0];i++){
if(srt[i]==PunctInitial)continue;
while( stiv[0]>=2 && unghi(stiv[stiv[0]-1],stiv[stiv[0]],srt[i])>0 )
--stiv[0];
stiv[++stiv[0]]=srt[i];
}
stiv[++stiv[0]]=PunctInitial;
printf("%d\n",stiv[0]-1);
reverse(stiv+1,stiv+1+stiv[0]);
for(i=1;i<=stiv[0]-1;i++)
printf("%lf %lf\n",x[stiv[i]],y[stiv[i]]);
return 0;
}