Pagini recente » Cod sursa (job #1607780) | Cod sursa (job #1613081) | Cod sursa (job #2726582) | Cod sursa (job #1602907) | Cod sursa (job #1166367)
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#define M 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct coord
{
long double x,y;
long double tg;
};
coord L[200001];
long double minx=M,miny=M;
int stiv[200001],n,sf;
int cmp(coord a,coord b)
{
return a.tg>b.tg;
}
void muta(long double &x,long double &y)
{
x=x-minx;
y=y-miny;
}
void citire()
{ int i,poz;
long double xx,yy;
f>>n;
for(i=1;i<=n;i++)
{
f>>xx>>yy;
L[i].x=xx;
L[i].y=yy;
if(minx>xx)
{
minx=xx;
miny=yy;
poz=i;
}
else
if(minx==xx)
if(miny>yy)
{
miny=yy;
poz=i;
}
}
swap(L[n],L[poz]);n--;
for(i=1;i<=n;i++)muta(L[i].x,L[i].y);
for(i=1;i<=n;i++)L[i].tg=atan2(L[i].y,L[i].x);
sort(L+1,L+n+1,cmp);
}
long double det(coord a,coord b,coord c)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
void infasuratoare()
{
int i;
stiv[1]=1;sf=1;
for(i=2;i<=n;i++)
{
while(sf>=1&&det(L[stiv[sf-1]],L[i],L[stiv[sf]])<0)sf--;
stiv[++sf]=i;
}
}
void afisare()
{ int i;
g<<sf+1<<'\n';
minx=-minx;miny=-miny;
for(i=0;i<=n;i++)muta(L[i].x,L[i].y);
for(i=sf;i>=0;i--)
g<<fixed<<setprecision(12)<<L[stiv[i]].x<<" "<<L[stiv[i]].y<<'\n';
}
int main()
{
citire();
infasuratoare();
afisare();
return 0;
}