Pagini recente » Cod sursa (job #462585) | Cod sursa (job #404051) | Cod sursa (job #2480087) | Cod sursa (job #1424571) | Cod sursa (job #702160)
Cod sursa(job #702160)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 120010
#define inf 1<<30
using namespace std;
double X[maxn],Y[maxn];
int n,pi;
double xpi,ypi;
int IND[maxn];
int ST[maxn];
bool cmp(int i,int j)
{
return ((double)((Y[i]-Y[pi])*(X[j]-X[pi]))> ((double)((X[i]-X[pi])*(Y[j]-Y[pi]))));
}
long double semn(int i1,int i2,int i3)
{
return (long double)(X[i1]*Y[i2]+X[i2]*Y[i3]+X[i3]*Y[i1]-X[i3]*Y[i2]-X[i1]*Y[i3]-X[i2]*Y[i1]);
}
void read()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
pi=0;
xpi=inf,ypi=inf;
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&X[i],&Y[i]);
if(xpi>X[i]) xpi=X[i],ypi=Y[i],pi=i;
else if(X[i]==xpi && Y[i]<ypi) ypi=Y[i],pi=i;
}
for(int i=1;i<=n;i++)
{
if(i==pi) continue;
else IND[++IND[0]]=i;
}
}
void solve()
{
sort(IND+1,IND+IND[0]+1,cmp);
ST[++ST[0]]=pi;
for(int i=1;i<=IND[0];i++)
{
while(ST[0]>2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i])>0)
ST[0]--;
ST[++ST[0]]=IND[i];
}
}
int main()
{
read();
freopen("infasuratoare.out","w",stdout);
solve();
printf("%d\n",ST[0]);
printf("%lf %lf\n",xpi,ypi);
for(int i=2;i<=ST[0];i++)
printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
}