Pagini recente » Cod sursa (job #1239513) | Cod sursa (job #875430) | Cod sursa (job #753941) | Cod sursa (job #2264709) | Cod sursa (job #3002634)
#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(12)<<a[st[i]].x;
g<<" ";
g<<fixed<<setprecision(12)<<a[st[i]].y<<'\n';
}
return 0;
}