Cod sursa(job #2563706)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 1 martie 2020 13:41:23
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#define eps 0.000000000001d

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

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

struct Punct
{
    double x, y;

    bool operator < (const Punct& other) const
    {
        if (fabs(y - other.y) < eps)
            return x < other.x;
        return y < other.y;
    }
};

int n, top, Stk[120001];
Punct A[120001];

double Prod(const Punct& p1, const Punct& p2, const Punct& p3)
{
    return (p1.x - p2.x) * (p1.y - p3.y) - (p1.x - p3.x) * (p1.y - p2.y);
}

bool SortF(const Punct& p1, const Punct& p2)
{
    return Prod(A[1], p1, p2) > 0.0d;
}

void Solve()
{
    Stk[1] = 1, Stk[2] = 2;
    top = 2;
    for (int i = 3; i <= n; ++i)
    {
        while (Prod(A[Stk[top - 1]], A[Stk[top]], A[i]) < 0)
            --top;
        Stk[++top] = i;
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> A[i].x >> A[i].y;
        if (A[i] < A[1])
            swap(A[i], A[1]);
    }
    sort(A + 2, A + n + 1, SortF);
    Solve();
    for (int i = 1; i <= top; ++i)
        fout << fixed << setprecision(7) << A[Stk[i]].x << " " << A[Stk[i]].y << '\n';

    return 0;
}