Pagini recente » Cod sursa (job #3266499) | Cod sursa (job #1968269) | Cod sursa (job #2373065) | Cod sursa (job #2870208) | Cod sursa (job #3277832)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
double x, y;
};
elem v[120009];
bool comp (elem x, elem y)
{
if (x.x<y.x) return 1;
if (x.x==y.x && x.y<y.y) return 1;
return 0;
}
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 st[120009], viz[120009], top, n;
void solve ()
{
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--;
}
st[++top]=i;
viz[i]=1;
}
}
int main ()
{
f >> n;
for (int i=1; i<=n; i++)
f >> v[i].x >> v[i].y;
sort (v+1, v+n+1, comp);
solve();
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';
}