Cod sursa(job #2403690)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 11 aprilie 2019 19:39:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>
#define N 120010
#define PI 3.141592653

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct
{
    double x, y;
    double unghi;
};

int n, k;
int st[N], top;
punct a[N], sol[N];

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

double prod_Vectorial(punct p, punct m, punct q)
{
    double y1 = p.y - m.y;
    double y2 = p.y - q.y;
    double x1 = p.x - m.x;
    double x2 = p.x - q.x;
    return y2 * x1 - y1 * x2;
}

double dist(punct p, punct q)
{
    return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}

bool cmp(punct p, punct q)
{
    if (!prod_Vectorial(a[1], p, q))
        return dist(a[1], p) > dist(a[1], q);
    return prod_Vectorial(a[1], p, q) > 0;
}

void Sorteaza()
{
    int ind = 1;
    for (int i = 2; i <= n; i++)
        if (a[i].x < a[ind].x || (a[i].x == a[ind].x && a[i].y < a[ind].y))
            ind = i;
    swap(a[1], a[ind]);
    sort(a + 2, a + n + 1, cmp);
}

void Select()
{
    for (int i = 2; i <= n; i++)
    {
        if (a[i].y == a[1].y)
            a[i].unghi = 90;
        else
        {
            a[i].unghi = atan2(a[i].x - a[1].x, a[i].y - a[1].y) * 180 / PI;
            if (a[i].unghi < 0)
                a[i].unghi *= -1;
            else a[i].unghi = 180 - a[i].unghi;
        }
    }
    double first_ang = a[2].unghi, last_ang = a[n].unghi;
    int ind;
    for (int i = 2; i <= n; i++)
        if (a[i].unghi == first_ang)
            ind = i;
    for (int i = 2, j = ind; i < j; i++, j--)
    {
        punct aux = a[i];
        a[i] = a[j];
        a[j] = aux;
    }

    sol[++k] = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i].unghi == first_ang || a[i].unghi == last_ang)
            sol[++k] = a[i];
        else if (a[i].unghi != a[i - 1].unghi)
            sol[++k] = a[i];
    }
}

void Solve()
{
    st[1] = 1;
    st[2] = 2;
    top = 2;

    for (int i = 3; i <= k; i++)
    {
        while (top > 2 && prod_Vectorial(sol[st[top - 1]], sol[st[top]], sol[i]) < 0)
            top--;
        st[++top] = i;
    }

    for (int i = 1; i <= top; i++)
        fout << fixed << setprecision(9) << sol[st[i]].x << " " << sol[st[i]].y << "\n";

}

int main()
{
    Citire();
    Sorteaza();
    Select();
    Solve();
    return 0;
}