Pagini recente » Cod sursa (job #2305474) | Cod sursa (job #560754) | Cod sursa (job #2172705) | Cod sursa (job #2593904) | Cod sursa (job #1142618)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define M 2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct coord
{
long double x,y,tg;
};
coord L[120001];
int sol[120001],n,sf;
long double minx=M,miny=M;
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 x,y;
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
L[i].x=x;L[i].y=y;
if(minx>x)
{
minx=x;
miny=y;
poz=i;
}
else
if(minx==x)
if(miny>y)
{
miny=y;
poz=i;
}
}
for(i=poz;i<n;i++)L[i]=L[i+1];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);
}
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;
sol[0]=0;sol[1]=1;
sf=1;
for(i=2;i<=n;i++)
{
while(sf>=1&&det(L[sol[sf-1]],L[i],L[sol[sf]])<0)sf--;
sol[++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[sol[i]].x<<" "<<L[sol[i]].y<<'\n';
}
int main()
{
citire();
sort(L+1,L+n+1,cmp);
infasuratoare();
afisare();
return 0;
}