Cod sursa(job #2416801)

Utilizator akaprosAna Kapros akapros Data 28 aprilie 2019 11:36:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define maxN 120002
#define ty  double
#define eps 1e-12

using namespace std;

FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);

struct Point
{
    ty x, y;
    bool operator < (const Point &ot) const
    {
        if (fabs(x - ot.x) < eps) return y < ot.y;
        return x < ot.x;
    }
    ty CrossProd(const Point &O, const Point &B)
    {
        return (x - O.x) * (B.y - O.y) - (B.x - O.x) * (y - O.y);
    }
} v[maxN];
int n;

int head, st[maxN];
bool vis[maxN];

void ConvHull()
{
    sort(v, v + n);
    head = 2;
    vis[1] = true;
    st[0] = 0;
    st[1] = 1;
    int sgn = 1;
    for (int i = 0; i >= 0; i += sgn)
    {
        if (vis[i]) continue;
        while (head > 1 && v[st[head - 2]].CrossProd(v[st[head - 1]], v[i]) < eps)
            vis[st[-- head]] = false;
        st[head ++] = i;
        vis[i] = true;
        if (i == n - 1)
            sgn = -sgn;
    }
    -- head;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    ConvHull();
    printf("%d\n", head);
    for (int i = 0; i < head; ++ i)
        printf("%.12lf %.12lf\n", v[st[i]].x, v[st[i]].y);
    return 0;
}