Pagini recente » Cod sursa (job #1276993) | Cod sursa (job #1008278) | Cod sursa (job #1626316) | Cod sursa (job #421076) | Cod sursa (job #3032249)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005;
int mlx,mly;
struct Point{
double x,y;
};
bool cmp (Point p,Point b)
{
return (p.x-mlx)*(b.y-mly)>(b.x-mlx)*(p.y-mly);
}
Point a[Nmax];
bool isInside(int i,int j,int k)
{
return (a[k].x-a[i].x)*(a[j].y-a[i].y)>(a[j].x-a[i].x)*(a[k].y-a[i].y);
}
stack<int> s;
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
}
int mostleft=1;
for(int i=1;i<=n;i++)
{
if(a[i].x<a[mostleft].x)
{
mostleft=i;
}
if(a[i].x==a[mostleft].x)
{
if(a[i].y<a[mostleft].y)
{
mostleft=i;
}
}
}
Point aux=a[mostleft];
a[mostleft]=a[1];
a[1]=aux;
mlx=a[1].x;
mly=a[1].y;
sort(a+2,a+n+1,cmp);
s.push(1);
s.push(2);
for(int i=2;i<=n;i++)
{
int t=s.top();
s.pop();
int t2=s.top();
s.push(t);
while(isInside(i,s.top(),t2) && s.size()>=2)
{
s.pop();
t=s.top();
s.pop();
t2=s.top();
s.push(t);
}
s.push(i);
}
while(!s.empty())
{
fout<<setprecision(9)<<a[s.top()].x<<' '<<a[s.top()].y<<'\n';
s.pop();
}
return 0;
}