Pagini recente » Cod sursa (job #1088083) | Cod sursa (job #370807) | Cod sursa (job #2449347) | Cod sursa (job #342092) | Cod sursa (job #3349206)
#include <bits/stdc++.h>
#define double long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
double x, y;
bool operator < (const elem & other) const
{
return (x<other.x || (x==other.x && y<other.y));
}
};
elem v[200009];
bool viz[200009];
int st[200009], vf=0;
int det (elem a, elem b, elem c)
{
int x1=a.x, y1=a.y, x2=b.x, y2=b.y, x3=c.x, y3=c.y;
return x2*y3+x1*y2+y1*x3-x2*y1-x3*y2-y3*x1;
}
signed main ()
{
int n;
f >> n;
for (int i=1; i<=n; i++)
f >> v[i].x >> v[i].y;
sort (v+1, v+n+1);
st[++vf]=1;
st[++vf]=2;
viz[2]=1;
vf=2;
int i=3;
int pas=1;
while (!viz[1])
{
while (viz[i])
{
if (i==n)
pas=-1;
i+=pas;
}
while (vf>=2 && det (v[st[vf-1]], v[st[vf]], v[i])<0)
{
viz[st[vf]]=0;
vf--;
}
viz[i]=1;
st[++vf]=i;
}
g << vf-1 <<'\n';
for (int i=2;i<=vf; i++)
g << fixed << setprecision(8)<< v[st[i]].x << ' ' << v[st[i]].y << '\n';
}