Pagini recente » Cod sursa (job #1723058) | Cod sursa (job #1199669) | Cod sursa (job #2278474) | Cod sursa (job #816114) | Cod sursa (job #3245327)
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
float x, y;
int poz;
}v[120000];
bool cmp(punct a, punct b)
{
if (a.x < b.x)
return true;
else if (a.x > b.x)
return false;
else
return (a.y < b.y);
}
double arie(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
int st[120000], vf;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
for(int i=2;i<n;i++)
{
if(arie(v[1], v[n], v[i]) < 0)
v[i].poz = 1;
else
v[i].poz = -1;
}
//jos( -1 )
st[1] = 1;
vf=1;
for(int i=2;i<n;i++)
{
if(v[i].poz == 1)
{
if(st[vf] == 1)
st[++vf] = i;
else
{
bool ok = true;
while(st[vf] != 1 && ok == true)
{
if(arie(v[st[vf-1]], v[st[vf]], v[i]) < 0)
vf--;
else
{
ok = false;
st[++vf] = i;
}
}
if(ok == true)
st[++vf] = i;
}
}
}
//sus( 1 )
st[++vf] = n;
for(int i=n-1;i>1;i--)
{
if(v[i].poz == -1)
{
if(st[vf] == n)
st[++vf] = i;
else
{
bool ok = true;
while(st[vf] != n && ok == true)
{
if(arie(v[st[vf-1]], v[st[vf]], v[i]) < 0)
vf--;
else
{
ok = false;
st[++vf] = i;
}
}
if(ok == true)
st[++vf] = i;
}
}
}
for (int i=2; i<=vf; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
cout << fixed << setprecision(6) << v[st[1]].x << " " << v[st[1]].y << '\n';
return 0;
}