Pagini recente » Cod sursa (job #2985742) | Cod sursa (job #1830768) | Cod sursa (job #2878746) | Cod sursa (job #3170242) | Cod sursa (job #2210164)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct pct
{
double x,y;
bool p;
}v[120003];
int st[120003],st1[120003];
bool cmp (pct a, pct b)
{
if(a.y<b.y)
return true;
if(a.y>b.y)
return false;
if(a.x<b.x)
return true;
return false;
}
bool prt (double x1, double y1, double x2, double y2, double x, double y)
{
if(x1*y2+x2*y+x*y1<x*y2+x1*y+x2*y1)
return 1;
return 0;
}
int main()
{
int n,i,k=0,s=0,k1;
double a,b;
in>>n;
for(i=1;i<=n;++i)
in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
st[++k]=1;
for(i=2;i<n;++i)
v[i].p=prt(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y);
for(i=2;i<=n;++i)
{
if(v[i].p==1 || i==n)
{
while(k>1 && prt(v[st[k-1]].x,v[st[k-1]].y,v[st[k]].x,v[st[k]].y,v[i].x,v[i].y)==1)
--k;
st[++k]=i;
}
}
k1=k;
s+=k;
k=0;
st1[++k]=1;
for(i=2;i<=n;++i)
{
if(v[i].p==0 || i==n)
{
while(k>1 && prt(v[st1[k-1]].x,v[st1[k-1]].y,v[st1[k]].x,v[st1[k]].y,v[i].x,v[i].y)==0)
--k;
st1[++k]=i;
}
}
s+=k;
out<<s-2<<'\n';
for(i=1;i<=k1;++i)
out<<fixed<<setprecision(12)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
for(i=k-1;i>1;--i)
out<<fixed<<setprecision(12)<<v[st1[i]].x<<' '<<v[st1[i]].y<<'\n';
return 0;
}