Pagini recente » Cod sursa (job #1909636) | Cod sursa (job #2153325) | Cod sursa (job #2823337) | Cod sursa (job #966484) | Cod sursa (job #1509848)
#include <bits/stdc++.h>
#define eps 1e-12
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{double x,y;} a[120004],st[120004],st2[120004];
bool cmp(point a, point b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
double cross_product(point o, point a, point b)
{
a.x-=o.x;
a.y-=o.y;
b.x-=o.x;
b.y-=o.y;
return (a.x*b.y-a.y*b.x);
}
int viz[120002];
int main()
{int n,i,vf=0;
in>>n;
for(i=1;i<=n;i++)
{
in>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
st[1]=a[1];
st[2]=a[2];
vf=2;
for(i=3;i<=n;i++)
{
while(vf>=2&&cross_product(st[vf-1],st[vf],a[i])<eps)
{
vf--;
}
st[++vf]=a[i];
}
int vf2;
st2[1]=a[n];
st2[2]=a[n-1];
vf2=2;
for(i=n-2;i>=1;i--)
{
while(vf2>=2&&cross_product(st2[vf2-1],st2[vf2],a[i])<eps)
{
vf2--;
}
st2[++vf2]=a[i];
}
out<<vf+vf2-2<<'\n';
for(i=1;i<=vf;i++)
out<<setprecision(6)<<fixed<<st[i].x<<" "<<st[i].y<<'\n';
for(i=2;i<vf2;i++)
out<<setprecision(6)<<fixed<<st2[i].x<<" "<<st2[i].y<<'\n';
return 0;
}