Pagini recente » Cod sursa (job #2576868) | Cod sursa (job #1283416) | Cod sursa (job #2576898) | Cod sursa (job #1876104) | Cod sursa (job #2284430)
#include <iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define pp pair< double, double >
#define x first
#define y second
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i,n,st[120010],niv,val,aux;
pp v[120010];
double determinant(pp a, pp b, pp c)
{
int ans=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
return ans;
}
int main()
{
fin>>n;
for(i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1);
st[1]=1; st[2]=2; niv=3;
for(i=3; i<=n; i++)
{
val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
if(val>=0)
{
st[niv]=i;
niv++;
}
else
{
if(niv==3)
{
st[2]=i;
}
else
{
while(val<0 && niv>2)
{
niv--;
val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
}
st[niv]=i;
niv++;
}
}
}
aux=niv-1;
st[niv]=n-1;
niv++;
for(i=n-2; i>=1; i--)
{
val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
if(val>=0)
{
st[niv]=i;
niv++;
}
else
{
if(niv-aux==2)
{
st[niv-1]=i;
}
else
{
while(val<0 && niv>aux+1)
{
niv--;
val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
}
st[niv]=i;
niv++;
}
}
}
niv--;
fout<<niv-1<<'\n';
for(i=2; i<=aux; i++)
fout<<setprecision(6)<<fixed<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
for(i=aux+1; i<=niv; i++)
fout<<setprecision(6)<<fixed<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
return 0;
}