Pagini recente » Cod sursa (job #2350445) | Cod sursa (job #971864) | Cod sursa (job #1470239) | Cod sursa (job #508723) | Cod sursa (job #1806937)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct{
long double x,y;
};
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
punct stiva[120000];
int compara(punct a,punct b)
{
return (a.x<b.x) || (a.x==b.x && a.y<b.y);
}
int n,vf=1;
punct a[120000];
int compara2(punct a,punct b)
{
long double m1=a.y;
long double m2=b.y;
m1=m1/(a.x);
if(a.x==0)
m1=3;
m2=m2/(b.x);
if(b.x==0)
m2=3;
return m1>=m2;
}
char sarie(punct a,punct b,punct c)
{
long double z;
z=a.x*b.y+b.x*c.y+a.y*c.x;
z=z-b.y*c.x-a.y*b.x-c.y*a.x;
if(z>-0.00000001)
return 1;
return 0;
}
void solution()
{
int i,j;
for(i=2;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(sarie(stiva[vf],a[i],a[j])==1)
{
i=j;
}
}
while(vf>=2 &&sarie(stiva[vf-1],stiva[vf],a[i])==1)
vf--;
stiva[++vf]=a[i];
}
}
int main()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+1+n,compara);
stiva[1].x=a[1].x;
stiva[1].y=a[1].y;
for(i=2;i<=n;i++)
{
a[i].x-=a[1].x;
a[i].y-=a[1].y;
}
sort(a+2,a+1+n,compara2);
for(i=2;i<=n;i++)
{
a[i].x+=a[1].x;
a[i].y+=a[1].y;
}
solution();
fout<<vf<<'\n';
for(i=1;i<=vf;i++)
fout<<setprecision(6)<<stiva[i].x<<' '<<setprecision(6)<<stiva[i].y<<'\n';
return 0;
}