Cod sursa(job #2442579)

Utilizator akaprosAna Kapros akapros Data 24 iulie 2019 13:32:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <bits/stdc++.h>
#define maxN 120002
#define ld double
#define x first
#define y second
#define Point pair < ld, ld >
#define Sit set<Point>::iterator
using namespace std;

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

int n;

ld CrossProd(Point A, Point B, Point C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

struct DynCHull
{
    set < Point > Up, Dw;
    bool bad(Sit it, set < Point > &s)
    {
        if (s.size() <= 2) return false;
        if (it == s.begin()) return false;
        if (++ it == s.end()) return false;
        auto C = it, B = -- it, A = -- it;
        return (CrossProd(*A, *B, *C) < 0);
    }
    void check_prv(Sit it, set < Point > &s)
    {
        if (s.begin() == it) return ;
        -- it;

        while (bad(it, s))
        {
            auto tmp = it;
            ++ it;
            s.erase(tmp);
        }
    }
    void check_nxt(Sit it, set < Point > &s)
    {
        if (++ it == s.end()) return ;
        while (bad(it, s))
        {
            auto tmp = it;
            ++ it;
            s.erase(tmp);
        }

    }
    void Insert(Point p, set <Point> &s)
    {
        auto it = s.insert(p).first;
        if (s.size() <= 2) return ;
        if (bad(it, s))
        {
            s.erase(it);
            return ;
        }
        check_prv(it, s);
        check_nxt(it, s);
    }
    void AddPoint(Point p)
    {
        Insert(p, Up);
        Insert({-p.x, -p.y}, Dw);
    }
} Ch;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
    {
        Point p;
        scanf("%lf %lf", &p.x, &p.y);
        Ch.AddPoint(p);
    }

    auto it = Ch.Up.end();
    -- it;
    Ch.Up.erase(it);
    it = Ch.Dw.end();
    -- it;
    Ch.Dw.erase(it);

    printf("%d\n", Ch.Up.size() + Ch.Dw.size());
    for (auto it = Ch.Up.begin(); it != Ch.Up.end(); ++ it)
        printf("%.9lf %.9lf\n", it->x, it->y);
    for (auto it = Ch.Dw.begin(); it != Ch.Dw.end(); ++ it)
        printf("%.9lf %.9lf\n", -it->x, -it->y);
    return 0;
}