Pagini recente » Borderou de evaluare (job #3332206) | Cod sursa (job #3331679) | Cod sursa (job #3311610) | Cod sursa (job #1000685) | Cod sursa (job #3348763)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N=12e4+5;
struct point
{
double x,y;
bool operator<(const point& e) const
{
return (y<e.y)||(y==e.y && x<e.x);
}
}v[N];
int sign(point a,point b,point c)
{
double r=a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
if(!r) return 0;
return (r<0)?-1:1;
}
bool cmp(point a,point b)
{
return sign(v[1],a,b)<0;
}
int n,i,j,s[N],ss;
double x,y;
int main()
{
///Sorting is negative
///Convex Hull is pozitive
fin>>n;
for(i=1;i<=n;++i)
{
fin>>x>>y;
v[i]={x,y};
}
point mn=v[1];
int poz=1;
for(i=2;i<=n;++i)
{
if(v[i]<mn)
{
mn=v[i];
poz=i;
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
///1 is eternal
s[1]=1; s[2]=2;
ss=2;
for(i=3;i<=n;++i)
{
//cout<<v[i].y<<'\n';
while(ss>=2 && sign(v[s[ss-1]],v[s[ss]],v[i])>0)
--ss;
s[++ss]=i;
}
fout<<fixed;
fout<<ss<<'\n';
fout<<setprecision(6)<<v[1].x<<' '<<v[1].y<<'\n';
for(int i=ss;i>=2;--i)
fout<<setprecision(6)<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
return 0;
}