Cod sursa(job #2355793)

Utilizator DavidLDavid Lauran DavidL Data 26 februarie 2019 12:31:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

const int NMAX = 120005;

int n;
pair <ld, ld> x[NMAX];
pair <ld, ld> sus[NMAX], jos[NMAX];
int kSus, kJos;

ld dist(pair <ld, ld> A, pair <ld, ld> B)
{
    return sqrt(abs(A.first - B.first) * abs(A.first - B.first) + abs(A.second - B.second) * abs(A.second - B.second));
}

long double panta(pair <ld, ld> A, pair <ld, ld> B)
{
    long double ret = abs(A.first - B.first) / dist(A, B);
    if (B.second > A.second)
        ret = 1 + 1 - ret;
    return ret;
}

int main()
{
    fi >> n;
    for (int i = 1; i <= n; i++)
    {
        fi >> x[i].first >> x[i].second;
    }

    sort(x + 1, x + n + 1);

    jos[++kJos] = x[1];
    sus[++kSus] = x[1];

    for (int i = 2; i <= n; i++)
    {
        /*if (x[i].first == 10 && x[i].second == -3)
        {
            if (panta(x[1], x[i]) > panta(x[1], x[n]))
                cout << "SUS";
            else
                cout << "JOS";
        }*/

        if (panta(x[1], x[i]) > panta(x[1], x[n])  || i == n) // sus
        {
            while (kSus > 1 && panta(sus[kSus - 1], sus[kSus]) < panta(sus[kSus - 1], x[i]))
                kSus--;
            sus[++kSus] = x[i];
            //cout << x[i].first << ", " << x[i].second << " este sus cu panta: " << panta(x[1], x[i]) <<"\n";
        }
        if (panta(x[1], x[i]) < panta(x[1], x[n]) || i == n) // jos
        {
            while (kJos > 1 && panta(jos[kJos - 1], jos[kJos]) > panta(jos[kJos - 1], x[i]))
                kJos--;
            jos[++kJos] = x[i];
            //cout << x[i].first << ", " << x[i].second << " este jos cu panta: " << panta(x[1], x[i]) << "\n";
        }
    }

    fo << kSus + kJos - 2 << "\n";

    for (int i = 2; i <= kJos; i++)
        fo << fixed << setprecision(15) << jos[i].first << " " << jos[i].second << "\n";
    for (int i = kSus - 1; i >= 1; i--)
        fo << fixed << setprecision(15) << sus[i].first << " " << sus[i].second << "\n";

    return 0;
}