Pagini recente » Cod sursa (job #1773515) | Cod sursa (job #1359532) | Cod sursa (job #1625798) | Cod sursa (job #1043138) | Cod sursa (job #430973)
Cod sursa(job #430973)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define NM 120005
#define DL long double
#define LL long long
#define inf 2000000000
double X[NM],Y[NM];
int N,PI,P[NM],STK[NM];
bool cmpu(int i,int j)
{
return (DL)(Y[i]-Y[PI])*(X[j]-X[PI])<(DL)(Y[j]-Y[PI])*(X[i]-X[PI]);
}
DL semn(int i1,int i2,int i3)
{
DL plus=(DL)X[i1]*Y[i2]+(DL)X[i2]*Y[i3]+(DL)X[i3]*Y[i1];
DL minus=(DL)Y[i1]*X[i2]+(DL)Y[i2]*X[i3]+(DL)Y[i3]*X[i1];
return plus-minus;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
X[0]=inf;
for(int i=1;i<=N;++i)
{
scanf("%lf %lf",&X[i],&Y[i]);
if(X[PI]>X[i] || (X[PI]==X[i] && Y[PI]>Y[i])) PI=i;
}
//printf("%d\n",PI);
for(int i=1;i<=N;++i)
if(i!=PI) P[++P[0]]=i;
sort(P+1,P+P[0]+1,cmpu);
/*
for(int i=1;i<=P[0];++i)
printf("%d ",P[i]);
printf("\n");
*/
STK[0]=1;
STK[1]=PI;
for(int i=1;i<=P[0];++i)
{
int pct=P[i];
while(STK[0]>=2 && semn(STK[STK[0]-1],STK[STK[0]],pct)<=0) --STK[0];
STK[++STK[0]]=pct;
}
printf("%d\n",STK[0]);
for(int i=1;i<=STK[0];++i)
printf("%lf %lf\n",X[STK[i]],Y[STK[i]]);
return 0;
}