Pagini recente » Cod sursa (job #2891677) | Cod sursa (job #3154824) | Cod sursa (job #389233) | Cod sursa (job #2693829) | Cod sursa (job #3300601)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct P
{
long double x,y;
}v[150005];
int n,s[150005],top,pos;
long double xmin,ymin=1e18L;
int comp(const P &a,const P &b)
{
return a.x*b.y>=b.x*a.y;
}
bool convex(P a,P b,P c)
{
long double r=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
return r>0;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<ymin)
{
ymin=v[i].y;
xmin=v[i].x;
pos=i;
}
}
for(int i=1;i<=n;i++)
{
v[i].x-=xmin;
v[i].y-=ymin;
}
swap(v[1],v[pos]);
sort(v+2,v+n+1,comp);
s[1]=1;
s[2]=2;
top=2;
for(int i=3;i<=n;i++)
{
while(top>=3&&!convex(v[s[top-1]],v[s[top]],v[i]))top--;
s[++top]=i;
}
fout<<top<<endl;
fout<<fixed<<setprecision(10);
for(int i=1;i<=top;i++)
fout<<v[s[i]].x+xmin<<' '<<v[s[i]].y+ymin<<endl;
return 0;
}