Pagini recente » Cod sursa (job #1956013) | Cod sursa (job #1783242) | Cod sursa (job #2755314) | Cod sursa (job #238646) | Cod sursa (job #1375369)
#include <cstdio>
#include <algorithm>
#include <stack>
#define f first
#define s second
using namespace std;
pair <double, double> v[120010];
bool frq[120010];
int st[120010];
bool det (pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
double d = 1.0 * a.f * b.s + 1.0 * b.f * c.s + 1.0 * a.s * c.f - 1.0 * c.f * b.s - 1.0 * b.f * a.s - 1.0 * c.s * a.f;
return (d < 0.0);
}
int main ()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int n;
scanf ("%d", &n);
for (int i = 1; i <= n; ++i)
scanf ("%lf %lf", &v[i].f, &v[i].s);
sort (v + 1, v + n + 1);
st[1] = 1;
st[0] = st[2] = 2;
frq[2] = true;
int i = 3, p = 1;
while (!frq[1])
{
while (frq[i])
{
if (i == n) p = -1;
i += p;
}
while (st[0] > 1 && !det (v[st[st[0] - 1]], v[st[st[0]]], v[i]))
frq[st[st[0]--]] = false;
st[++st[0]] = i;
frq[i] = true;
}
--st[0];
printf ("%d\n", st[0]);
for (int i = 1; i <= st[0]; ++i)
printf ("%lf %lf\n", v[st[i]].f, v[st[i]].s);
return 0;
}