Pagini recente » Cod sursa (job #3292980) | Cod sursa (job #3278524) | Cod sursa (job #3293722) | Cod sursa (job #3293635) | Cod sursa (job #3293884)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
double x, y;
}v[120009];
int st[120009];
bool viz[200009];
int top;
bool comp (const elem & x, const elem & y)
{
return ((x.x<y.x) || (x.x==y.x && x.y<y.y));
}
double 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 n;
f >> n;
for (int i=1; i<=n; i++)
{
f >> v[i].x >> v[i].y;
}
sort (v+1, v+n+1, comp);
st[1]=1, st[2]=2, viz[2]=1, top=2;
int pas=1;
int i=3;
while (!viz[1])
{
while (viz[i])
{
if (i==n) pas=-1;
i+=pas;
}
while (top >=2 && panta (v[st[top-1]], v[st[top]], v[i])<0)
{
viz[st[top]]=0;
top--;
}
viz[i]=1;
st[++top]=i;
}
g << top-1 << '\n';
for (int i=2; i<=top; i++)
g << fixed << setprecision(8) << v[st[i]].x << ' ' << fixed << setprecision(8) << v[st[i]].y << '\n';
}