Pagini recente » Cod sursa (job #3344067) | Cod sursa (job #2187628) | Cod sursa (job #3307649) | Cod sursa (job #1947747) | Cod sursa (job #3344637)
#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.y);
}
}v[N];
int n,i,j,s[N],sz;
double x,y;
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 main()
{
fin>>n;
point mn={2e9,2e9};
int poz=0;
for(i=1;i<=n;++i)
{
fin>>x>>y;
v[i]={x,y};
if(v[i]<mn)
{
mn=v[i];
poz=i;
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
s[1]=1;
s[2]=2;
sz=2;
for(i=3;i<=n;++i)
{
while(sz>=2 && sign(v[s[sz-1]],v[s[sz]],v[i])>0)
--sz;
s[++sz]=i;
}
fout<<fixed;
fout<<sz<<'\n';
fout<<setprecision(9)<<v[1].x<<' '<<v[1].y<<'\n';
for(i=sz;i>=2;--i)
{
int j=s[i];
fout<<setprecision(9)<<v[j].x<<' '<<v[j].y<<'\n';
}
return 0;
}