Pagini recente » Cod sursa (job #3255070) | Cod sursa (job #2198651) | Cod sursa (job #806397) | Cod sursa (job #650208) | Cod sursa (job #3002630)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct pct
{
double x,y;
} a[120005];
int st[120005];
bool viz[120005];
bool cmp(pct X,pct Y)
{
if(X.x==Y.x)
return X.y<Y.y;
return X.x<Y.x;
}
bool determinat(pct a,pct b, pct c)
{
return (c.y-a.y)*(b.x-a.x)>(c.x-a.x)*(b.y-a.y);
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
int vf=2;
viz[2]=true;
int i=3,poz=1;
while(viz[1]==false)
{
if(!viz[i])
{
while(vf>1&& determinat(a[st[vf-1]],a[st[vf]],a[i])&&st[vf]!=n)
viz[st[vf]]=false,vf--;
st[++vf]=i;
viz[i]=true;
}
if(i==n)
poz=-1;
i+=poz;
}
vf--;
g<<vf<<'\n';
for(int i=1;i<=vf;i++)
g<<fixed<<setprecision(9)<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
return 0;
}