Pagini recente » Cod sursa (job #1170550) | Cod sursa (job #83095) | Cod sursa (job #1096404) | Cod sursa (job #3216446) | Cod sursa (job #2556983)
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 120005
#define PI 3.1415926535897932384626433832795
using namespace std;
typedef long long ll;
ll n, i, j, xmin, ymin, k, pz;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct frac
{
long double x, y;
int p;
}f[N];
struct punct
{
long double x, y;
}p[N], st[N];
bool comp(frac a, frac b)
{
return a.x>b.x;
}
long double arie(punct a, punct b, punct c)
{
long double m[3][3]={{a.x,a.y,1},{b.x,b.y,1},{c.x,c.y,1}};
return (m[0][0]*m[1][1]*m[2][2] + m[0][1]*m[1][2]*m[2][0]+m[0][2]*m[1][0]*m[2][1])-
(m[0][2]*m[1][1]*m[2][0]+m[2][1]*m[1][2]*m[0][0]+m[2][2]*m[1][0]*m[0][1]);
}
void fast()
{
ios_base::sync_with_stdio(false);
cin.tie();
}
int main()
{
fast();
fin>>n;
ymin=2000000000;
for(i=1;i<=n;++i)
{
fin>>p[i].x>>p[i].y;
if(p[i].y<ymin||(p[i].y==ymin&&p[i].x<xmin))
{
xmin=p[i].x;
ymin=p[i].y;
pz=i;
}
}
// swap(p[pz],p[n]);
// --n;
for(i=1;i<=n;++i)
if(i!=pz)
{
f[i].p=i;
ll Dx=+p[i].x-p[pz].x;
ll Dy=+p[i].y-p[pz].y;
f[i].x=abs(Dy);
f[i].y=abs(Dx);
if(f[i].y==0)
f[i].x=90;
else
f[i].x=atan(f[i].x/f[i].y)*180/PI;
if(Dx<0&&Dy<0)
f[i].x+=180;
else if(Dx<0)
f[i].x=180-f[i].x;
else if(Dy<0)f[i].x=360-f[i].x;
// cout<<f[i].x<<' '<<p[i].x<<' '<<p[i].y<<'\n';
}
//cout<<pz;
swap(f[pz],f[n]);
--n;
sort(f+1,f+n+1,comp);
//for(i=1;i<=n;++i)
// cout<<p[f[i].p].x<<' '<<p[f[i].p].y<<'\n';
++k;
// f[n+1].p=pz;
st[k]=p[pz];
// cerr<<st[k].x<<' '<<st[k].y<<'\n';
++k;
st[k]=p[f[1].p];
//cerr<<st[k].x<<' '<<st[k].y<<'\n'<<'\n';
for(i=2;i<=n;++i)
{
while(k>1&&arie(st[k-1],st[k],p[f[i].p])>=0)
--k;
st[++k]=p[f[i].p];
// cout<<st[k].x<<' '<<st[k].y<<'\n';
}
fout<<k<<'\n';
for(i=1;i<=k;++i)
fout<<fixed<<setprecision(10)<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}