Pagini recente » lol_asd | Cod sursa (job #197242) | Cod sursa (job #84588) | Cod sursa (job #248443) | Cod sursa (job #1021419)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define punct pair<double,double>
#define x first
#define y second
#define N 120010
#define eps 0.000000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,l,vf,st[N],viz[N];
punct v[N];
inline double sarrus(punct c,punct a,punct b)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
{
f>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1);
st[1]=1;
st[2]=2;
vf=2;
viz[2]=1;
for(i=1,l=1;i;i+=l)
{
if(i==n)
l=-1;
if(viz[i])
continue;
while(vf>=2&&sarrus(v[st[vf-1]],v[st[vf]],v[i])<eps)
viz[st[vf--]]=0;
st[++vf]=i;
viz[i]=1;
}
g<<vf-1<<'\n'<<fixed<<setprecision(6);
for(i=1;i<vf;++i)
g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
return 0;
}