Pagini recente » Cod sursa (job #2367122) | Cod sursa (job #278663) | Cod sursa (job #363164) | Cod sursa (job #2848127) | Cod sursa (job #2310530)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long double ld;
struct point
{
ld x;
ld y;
};
ld cp(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
ld area(point p1,point p2,point p3)
{
return fabs(0.5*cp(p1,p2,p3));
}
point lolo;
ld dpp(point p1,point p2)
{
ld dx=p1.x-p2.x;
ld dy=p2.y-p2.y;
return dx*dx+dy*dy;
}
bool cmp_trigo(point p1,point p2)
{
if(cp(lolo,p1,p2)==0)
{
return dpp(lolo,p1)<dpp(lolo,p2);
}
else
{
return cp(lolo,p1,p2)>0;
}
}
int n;
const int N=120000+5;
point st[N];
int vf;
inline void add(point a)
{
while(vf>=2 && cp(st[vf-1],st[vf],a)<=0)
{
vf--;
}
st[++vf]=a;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
lolo={1000000000,1000000000};
cin>>n;
vector<point>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i].x>>v[i].y;
if(v[i].x<lolo.x)
{
lolo=v[i];
}
if(v[i].x==lolo.x && lolo.y<v[i].y)
{
lolo=v[i];
}
}
sort(v.begin(),v.end(),cmp_trigo);
for(int i=0;i<n;i++)
{
if(v[i].x==lolo.x && v[i].y==lolo.y)
{
swap(v[i],v[0]);
break;
}
}
for(int i=0;i<=n;i++)
{
add(v[i%n]);
}
cout<<vf-1<<"\n";
for(int i=1;i<vf;i++)
{
cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
}
return 0;
}
/**
{1}
**/