Pagini recente » Cod sursa (job #2369518) | Cod sursa (job #1428198) | Cod sursa (job #1355384) | Cod sursa (job #1366108) | Cod sursa (job #2883685)
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
double x,y;
};
elem v[120001];
int st[120001],viz[120001];
inline bool cmp(const elem &a, const elem &b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool panta(elem a, elem b, elem c)
{
return(c.y-a.y)*(b.x-a.x)<=(b.y-a.y)*(c.x-a.x);
}
int main()
{int i,n,vf,pas=1;
f>>n;
for (i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
st[1]=1;
st[2]=2;
vf=2;
viz[2]=1;
i=3;
while (viz[1]==0)
{ if (viz[i]==0)
{
while (vf>1 && panta(v[st[vf-1]],v[st[vf]],v[i])==1)
{
viz[st[vf]]=0;
vf--;
}
vf++;
st[vf]=i;
viz[i]=1;
}
if (i==n) pas=-1;
i+=pas;
}
vf--;
g<<vf<<'\n';
for (i=1;i<=vf;i++)
g<<fixed<<setprecision(12)<<v[st[i]].x<<' '<<fixed<<setprecision(12)<<v[st[i]].y<<'\n';
}