Pagini recente » Cod sursa (job #1551484) | Cod sursa (job #1580201) | Cod sursa (job #1279917) | Cod sursa (job #1041540) | Cod sursa (job #2453141)
#include <bits/stdc++.h>
#define NM 120005
#define EPS 1e-12
#define point pair<double,double>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,vf,st[NM];
point v[NM];
bool viz[NM];
void Read();
void ConvexHull();
bool cmp(point,point);
int cmp1(double,double);
int ok(point,point,point);
int main()
{ Read();
ConvexHull();
return 0;
}
void Read()
{ f>>n;
for(int i=1; i<=n; i++)
f>>v[i].x>>v[i].y;
}
void ConvexHull()
{ sort(v+1,v+n+1,cmp);
st[1]=1;
st[2]=2;
viz[1]=viz[2]=true;
vf=2;
bool aux=false;
for(int i=1; i; (!aux ? i++ : i--))
{ if(i==n)
aux=true;
if(!viz[i])
{ while(vf>=2 && ok(v[st[vf-1]],v[st[vf]],v[i])==-1)
viz[st[vf--]]=false;
st[++vf]=i;
viz[i]=true;
}
}
g<<vf-1<<'\n';
for(int i=vf-1; i; i--)
g<<fixed<<setprecision(6)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
int cmp1(double a,double b)
{ if(a+EPS<b)
return 1;
if(b+EPS<a)
return -1;
return 0;
}
bool cmp(point a,point b)
{ int ans=cmp1(a.x,b.x);
if(ans)
return ans==1;
return cmp1(a.y,b.y)==1;
}
int ok(point a,point b,point c)
{ double ans=(a.x*b.y+b.x*c.y+c.x*a.y)-(c.x*b.y+a.x*c.y+b.x*a.y);
return cmp1(ans,0);
}