Pagini recente » Cod sursa (job #750671) | Cod sursa (job #807733) | Cod sursa (job #2701145) | Cod sursa (job #2336085) | Cod sursa (job #2110557)
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#define INF 1999999999
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in), fout("infasuratoare.out",ios::out);
int n,k,lst;
struct punct
{
double x, y;
} v[DN],st[DN];
bool cmp(punct a, punct b)
{
if(a.x<=b.x) return 1;
return 0;
}
int det(punct a, punct b, punct c)
{
double x;
x=a.x*b.y+b.x*c.y+a.y*c.x;
x=x-c.x*b.y-a.y*b.x-c.y*a.x;
if(x<0) return -1;
if(x>0) return 1;
return 0;
}
int main()
{
int i;
double a, b;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a>>b;
v[i]={a, b};
}
sort(v+1,v+n+1,cmp);
st[lst=1]=v[1];
for(i=1;i<=n;i++)
{
while(lst>1 && det(st[lst-1],st[lst], v[i])<=0) lst--;
st[++lst]=v[i];
}
k=lst;
for(i=n;i>=1;i--)
{
while(lst>k && det(st[lst-1],st[lst], v[i])<=0) lst--;
st[++lst]=v[i];
}
fout<<fixed;
for(i=1;i<lst;i++)
{
fout<<st[i].x<<" "<<st[i].y<<"\n";
}
}