Pagini recente » Cod sursa (job #2191995) | Cod sursa (job #2630636) | Cod sursa (job #2553949) | Cod sursa (job #1901403) | Cod sursa (job #1334388)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define nmax 120010
int n,poz,varf;
struct point
{
double x,y;
}v[nmax],st[nmax];
double prod(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
int comp(point p1,point p2)
{
return prod(v[1],p1,p2)<0;
}
int main()
{
int i,j;
cin>>n;
cin>>v[1].x>>v[1].y;
poz=1;
for (i=2;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
if (v[i].x<v[poz].x)
poz=i;
else if (v[i].x==v[poz].x && v[i].y<v[poz].y)
poz=i;
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,comp);
st[1]=v[1];
st[2]=v[2];
varf=2;
for (i=3;i<=n;i++)
{
while (varf>=2 && prod(st[varf-1],st[varf],v[i])>0)
varf--;
st[++varf]=v[i];
}
cout<<fixed;
cout<<varf<<'\n';
for (i=varf;i;i--)
cout<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
}