Pagini recente » Cod sursa (job #1055550) | Cod sursa (job #3243280) | Cod sursa (job #192865) | Cod sursa (job #2945195) | Cod sursa (job #1614289)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define eps 1e-12
#define max_n 120050
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {double x,y;};
punct p[max_n+1],v[max_n+1];
int i,h,n,s[max_n+1],ok[max_n+1];
inline int cmp1 (double a,double b)
{ if(a+eps<b)
return 1;
if(b+eps<a)
return -1;
return 0;
}
bool cmp (const punct &a, const punct &b)
{ int t;
t=cmp1(a.x,b.x);
if(t!=0)
return t==1;
return (cmp1(a.y,b.y)==1);
}
int semn (punct a, punct b, punct c)
{
return cmp1(a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-c.y*a.x-a.y*b.x,0);
}
void rezolva()
{ int k,q;
sort(v+1,v+n,cmp);
s[1]=1;
s[2]=2;
ok[2]=1;
k=2;
i=3;
q=1;
while(1)
{ while(ok[i])
{if(i==n)
q=-1;
i=i+q;
}
while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
{ok[s[k]]=0;
k--;
}
s[++k]=i;
ok[i]=1;
if(ok[1]==1)
break;}
h=k-1;
}
int main()
{f>>n;
for(i=1;i<=n;++i)
f>>v[i].x>>v[i].y;
rezolva();
g<<h<<'\n';
g<<setprecision(6)<<fixed;
for(i=h;i>=1;--i)
g<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
return 0;
}