Pagini recente » Cod sursa (job #329136) | Cod sursa (job #2536842) | Cod sursa (job #1905747) | Cod sursa (job #130419) | Cod sursa (job #1410536)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define PI 3.14159265
using namespace std;
typedef double var;
struct puncte
{
var x,y,panta;
};
puncte v[120003];
struct axe
{
var x,y;
};
axe t[12000];
bool cmp(puncte a,puncte b)
{
if(a.panta<b.panta)
return 0;
if(a.panta==b.panta)
if(a.y<b.y)
return 1;
else
return 0;
return 1;
}
double determinant(axe a,axe b,puncte c)
{
return (a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-b.x*a.y-c.y*a.x);
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,k=0;
var a,b,minim=1000000010;
f>>n;
for(i=1;i<=n;i++)
{
f>>a>>b;
v[i].x=a;
v[i].y=b;
if(v[i].x<minim) minim=v[i].x;
}
if(minim<0)
{
for(i=1;i<=n;i++)
{
v[i].x+=minim;
v[i].panta=atan2(v[i].y,v[i].x);
}
}
else
for(i=1;i<=n;i++)
{
v[i].panta=atan2(v[i].y,v[i].x);
}
sort(v+1,v+n+1,cmp);
t[1].x=v[1].x;
t[1].y=v[1].y;
t[2].y=v[2].y;
t[2].x=v[2].x;
k=2;
int j;
for(i=3;i<=n;i++)
{
if(determinant(t[k-1],t[k],v[i])<0)
{
k+=1;
t[k].x=v[i].x;
t[k].y=v[i].y;
}
else
{
t[k].x=v[i].x;
t[k].y=v[i].y;
}
}
g<<k<<'\n';
if(minim<0)
for(i=k;i>=1;i--)
{
g<<setprecision(6)<<fixed<<t[i].x-minim<<" "<<t[i].y<<'\n';
}
else
for(i=k;i>=1;i--)
{
g<<setprecision(6)<<fixed<<t[i].x<<" "<<t[i].y<<'\n';
}
f.close();
g.close();
return 0;
}