Pagini recente » Cod sursa (job #2959194) | Cod sursa (job #2677120) | Cod sursa (job #2603041) | Cod sursa (job #1042278) | Cod sursa (job #3268075)
#include <bits/stdc++.h>
#define double long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N=120005,inf=2e9;
struct elem
{
double x,y;
}v[N];
int n,i,j,x,y,s[N],sz;
elem sol[N];
double det(double x,double y,double x2,double y2,double x3,double y3)
{
return x*y2+x2*y3+x3*y-x3*y2-x*y3-x2*y;
}
bool cmp(elem a,elem b)
{
double dy1=a.y-y;
double dy2=b.y-y;
double dx1=a.x-x;
double dx2=b.x-x;
double cad1,cad2;
if(!dy1) cad1=0.5;
else if(dx1<0) cad1=2;
else if(!dx1) cad1=1.5;
else if(dx1>0) cad1=1;
if(!dy2) cad2=0.5;
else if(dx2<0) cad2=2;
else if(!dx2) cad2=1.5;
else if(dx2>0) cad2=1;
if(cad1!=cad2)
return cad1<cad2;
else
return dy1*dx2<dx1*dy2;
}
void read()
{
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
}
}
void init()
{
x=inf;
y=inf;
for(i=1;i<=n;++i)
{
if(v[i].y<y)
{
y=v[i].y;
j=i;
x=v[i].x;
}
else if(v[i].y==y && v[i].x<x)
{
x=v[i].x;
j=i;
}
}
swap(v[j],v[1]);
sort(v+2,v+n+1,cmp);
}
void print(double x)
{
fout<<fixed<<setprecision(6)<<x;
}
double solve()
{
sz=2;
s[1]=1;
s[2]=2;
for(i=3;i<=n;++i)
{
while(sz>=2 && det(v[i].x,v[i].y,v[s[sz]].x,v[s[sz]].y,v[s[sz-1]].x,v[s[sz-1]].y)>0)
{
--sz;
}
s[++sz]=i;
}
fout<<sz<<'\n';
x=y=0;
for(i=1;i<=sz;++i)
{
sol[i].x=v[s[i]].x;
sol[i].y=v[s[i]].y;
}
x=0; y=0;
sort(sol+1,sol+sz+1,cmp);
for(i=1;i<=sz;++i)
{
print(sol[i].x); fout<<' ';
print(sol[i].y); fout<<'\n';
}
}
int main()
{
read();
init();
solve();
return 0;
}