Pagini recente » Cod sursa (job #777817) | Cod sursa (job #1598609) | Cod sursa (job #1469589) | Cod sursa (job #258517) | Cod sursa (job #1509801)
#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];
bool cmp(point a, point b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
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 st[120002],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]=1;
st[2]=2;
vf=2;
for(i=3;i<=n;i++)
{
while(vf>=2&&cross_product(a[st[vf-1]],a[st[vf]],a[i])<eps)
{
vf--;
}
st[++vf]=i;
}
int st2[120002],vf2;
st2[1]=1;
st2[2]=2;
vf2=2;
for(i=n-2;i>=2;i--)
{
while(vf2>=2&&cross_product(a[st2[vf2-1]],a[st2[vf2]],a[i])<eps)
{
vf2--;
}
st2[++vf2]=i;
}
out<<vf+vf2-2<<'\n';
for(i=1;i<vf;i++)
out<<setprecision(6)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
for(i=1;i<vf2;i++)
out<<setprecision(6)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
return 0;
}