Cod sursa(job #2350711)

Utilizator akaprosAna Kapros akapros Data 21 februarie 2019 17:44:00
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <bits/stdc++.h>
#define maxN 120002
#define eps 0.000000001
using namespace std;

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

/* ------------------------------------------------------- */
int n;
struct Point
{
    double x, y;
    bool operator < (const Point &ot) const
    {
        if (fabs(x - ot.x) < eps)
            return y < ot.y;
        return x < ot.x;
    }
} v[maxN];
struct PolarPoint
{
    double r, alpha;
    bool operator < (const PolarPoint &ot) const
    {
        if (fabs(alpha - ot.alpha) < eps)
            return r > ot.r;
        return alpha > ot.alpha;
    }
} V[maxN];
/* ------------------------------------------------------- */
double CrossProd(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

Point PPtoP(PolarPoint p)
{
    double r = p.r, alpha = p.alpha;
    return {r * cos(alpha), r * sin(alpha)};
}

PolarPoint PtoPP(Point p)
{
    double x = p.x, y = p.y;
    double r = sqrt(x * x + y * y),
           alpha = atan2(y, x);
    //printf("%Lf %Lf %Lf %Lf\n", (long double)PPtoP({r, alpha}).x, (long double)PPtoP({r, alpha}).y, (long double)x, (long double)y);
    return {r, alpha};
}

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

void ConvHull()
{
    memset(vis, 0, sizeof(vis));
    st[0][1] = 1;
    st[0][2] = 2;
    head[0] = 2;
    vis[2] = true;

    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
    {
        if (vis[i]) continue;
        while (head[0] >= 2 && CrossProd(v[st[0][head[0] - 1]], v[st[0][head[0]]], v[i]) > eps)
            vis[st[0][head[0] --]] = false;
        st[0][++ head[0]] = i;
        vis[i] = true;
    }
    -- head[0];
}
void Convhull()
{
    sort(V + 2, V + n + 1);
    head[1] = 2;
    st[1][1] = 1;
    st[1][2] = 2;
    for (int i = 3; i <= n; ++ i)
    {
        while (head[1] > 1 && CrossProd(PPtoP(V[st[1][head[1] - 1]]), PPtoP(V[st[1][head[1]]]), PPtoP(V[i])) > -eps)
            -- head[1];
        st[1][++ head[1]] = i;
    }
}


int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    sort(v + 1, v + n + 1);
    V[1] = PtoPP({0, 0});
    for (int i = 2; i <= n; ++ i)
        V[i] = PtoPP({v[i].x - v[1].x, v[i].y - v[1].y});

    ConvHull();
    Convhull();
    /*if (head[0] != head[1])
        exit(0);*/
    int t = 0;
    printf("%d\n", head[t]);
    for (int i = 1; i <= head[t]; ++ i)
        printf("%Lf %Lf\n", (long double)v[st[0][i]].x, (long double)v[st[0][i]].y);

    return 0;
}