Cod sursa(job #2209101)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 1 iunie 2018 18:42:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

const double eps = 1e-12;

int pas, poz, st[120001], vf;

bool pus[120001];

struct punct
{
    double x, y;
};

punct a[120002];

bool cmp (punct q, punct w)
{
    if (q.x > w.x) return false;

    if (q.x == w.x && q.y > w.y) return false;

    return true;
}

double det (double x1, double y1, double x2, double y2, double x3, double y3)
{
    return (x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1);
}

int n;

int main()
{
    f >> n;

    for (int i = 1; i <= n; i++)
    {
        f >> a[i].x >> a[i].y;
    }

    sort(a+1,a+n+1,cmp);

    st[1] = 1;
    st[2] = 2;
    pus[2] = true;
    vf = 2;
    poz = 3;
    pas = 1;

    while (pus[1] == false)
    {
        while (pus[poz] == true) {
            if (poz == n) pas = -1;
            poz = poz + pas;
        }

        while (vf >= 2 && det(a[st[vf-1]].x,a[st[vf-1]].y,a[st[vf]].x,a[st[vf]].y,a[poz].x,a[poz].y) < 0)
        {
            pus[st[vf]] = false;
            vf--;
        }

        vf++;
        st[vf] = poz;
        pus[st[vf]] = true;
    }

    g << vf - 1 << '\n';

    g << setprecision(6) << fixed;

    for (int i = 2; i <= vf; i++)
    {
        g << a[st[i]].x << " " << a[st[i]].y << '\n';
    }
    return 0;
}