Pagini recente » Cod sursa (job #1127473) | Cod sursa (job #538116) | Cod sursa (job #1349410) | Cod sursa (job #716311) | Cod sursa (job #260200)
Cod sursa(job #260200)
#include<cstdio>
#include<algorithm>
#define MX 120001
#define oo 100000001
#include<vector>
using namespace std;
struct pct
{
double x,y;
double p(pct m)
{
return (double)(y-m.y)/(double)(x-m.x);
}
bool operator!=(pct a)
{
return x==a.x&&y==a.y?0:1;
}
bool operator==(pct a)
{
return x==a.x&&y==a.y?1:0;
}
};
pct a[MX],mn;
long n,k=1;
pct s[MX];
double sm(pct a,pct b, pct c)
{
long double x=(long double)(a.x*b.x+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y);
return x;
}
void rd()
{
mn.x=mn.y=oo;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
float x,y;
scanf("%f%f",&x,&y);
a[i].x=x,a[i].y=y;
if(mn.x>a[i].x)
mn=a[i];
else if(mn.x==a[i].x&&mn.y>a[i].y)
mn=a[i];
}
}
bool cmp(pct a,pct b)
{
return a.p(mn)<b.p(mn);
}
void go()
{
long i=2;
s[1]=mn;
if(a[1]==mn)
i++,s[++k]=a[2];
else
s[++k]=a[1];
for(;i<=n;i++)
if(a[i]!=mn)
{
while(sm(a[i],s[k-1],s[k])<0)
k--;
s[++k]=a[i];
}
}
void afisare()
{
printf("%ld\n",k);
for(long i=1;i<=k;i++)
printf("%f %f\n",s[i].x,s[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
rd();
sort(a+1,a+n+1,cmp);
go();
afisare();
return 0;
}