Pagini recente » Cod sursa (job #2017717) | Cod sursa (job #2517080) | Cod sursa (job #1086880) | Cod sursa (job #3261649) | Cod sursa (job #1336434)
#include <cstdio>
#include <algorithm>
#define NMAX 120010
#define eps 1e-12
using namespace std;
struct point
{
double x,y;
};
point v[NMAX];
bool ok[NMAX];
int n,i,H,s[NMAX];
int cmp1(double x,double y)
{
if(x+eps<y) return 1;
if(y+eps<x) return -1;
return 0;
}
bool cmp(point a, point b)
{
int t;
t=cmp1(a.x,b.x);
if(t!=0)
{
if(t==1) return true;
else return false;
}
else return(cmp1(a.y,b.y)==1);
}
bool semn(point a,point b,point c)
{
double p;
p=a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
return (cmp1(p,0)==1);
}
void rezolva()
{
int q;
sort(v+1,v+n+1,cmp);
s[1]=1;s[2]=2;s[0]=2;
ok[2]=true;
i=3;
q=1;
while(!ok[1])
{
while(ok[i])
{
if(i==n) q=-1;
i+=q;
}
while(s[0]>=2 && !semn(v[s[s[0]]],v[s[s[0]-1]],v[i]))
{
ok[s[s[0]--]]=false;
}
s[++s[0]]=i;
ok[s[s[0]]]=true;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;++i)
scanf("%lf %lf\n",&v[i].x,&v[i].y);
rezolva();
H=s[0]-1;
printf("%d\n",H);
for(i=1;i<s[0];++i)
printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
printf("\n");
return 0;
}