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