Cod sursa(job #3227199)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 27 aprilie 2024 00:35:00
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.61 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

#include <iomanip>

using namespace std;

const int NMAX = 120000;

const double INF = 1e10;

int n;
pair<double, double> pct[1 + NMAX];

vector<int> stiva;

double dist[1 + NMAX][1 + NMAX];

bool inInfasuratoare[1 + NMAX];

/*
    x1 y1 1
    x2 y2 1
    x3 y3 1

> 0 stanga, sens trigonometric
< 0 dreapta
= 0 coliniare

x1 y1 = origine vector
x2 y2 = varf vector
x3 y3 = punctul de testat
*/

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

inline double det(const pair<double, double>& pct1, const pair<double, double>& pct2, const pair<double, double>& pct3)
{
    return pct1.first * pct2.second + pct2.first * pct3.second + pct3.first * pct1.second - pct3.first * pct2.second - pct1.first * pct3.second - pct2.first * pct1.second;
}

bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
    // a apare inaintea lui b daca e la dreapta de vectorul [pct(n) b]
    return det(pct[n], b, a) <= 0;
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    in >> n;

    for (int i = 1; i <= n; ++i)
        in >> pct[i].first >> pct[i].second;

    long long xMinim = INF;
    long long yMinim = INF;
    int indexMinim = -1;
    for (int i = 1; i <= n; ++i)
    {
        if (pct[i].first < xMinim)
        {
            xMinim = pct[i].first;
            yMinim = pct[i].second;
            indexMinim = i;
        }
        else if (pct[i].first == xMinim)
        {
            if (pct[i].second < yMinim)
            {
                yMinim = pct[i].second;
                indexMinim = i;
            }
        }
    }

    swap(pct[n], pct[indexMinim]);
    sort(pct + 1, pct + 1 + n - 1, comp);

    stiva.push_back(n);
    for (int i = 1; i <= n; ++i)
    {
        while (stiva.size() >= 2 && det(pct[stiva[(int)stiva.size() - 2]], pct[stiva[(int)stiva.size() - 1]], pct[i]) <= 0)
            stiva.pop_back();

        stiva.push_back(i);
    }
    stiva.pop_back();

    // Avem infasuratoarea convexa

    out << stiva.size() << '\n';
    for (int i = 0; i < stiva.size(); ++i)
    {
        out << setprecision(6) << fixed << pct[stiva[i]].first << ' ';
        out << setprecision(6) << fixed << pct[stiva[i]].second <<'\n';
    }
    out << '\n';

    /*
    for (int i = 1; i <= n; ++i)
    {
        dist[i][i] = 0.0;

        for (int j = i + 1; j <= n; ++j)
        {
            dist[i][j] = sqrt(1.0 * (pct[i].first - pct[j].first) * (pct[i].first - pct[j].first) + 1.0 * (pct[i].second - pct[j].second) * (pct[i].second - pct[j].second));
            dist[j][i] = dist[i][j];
        }
    }

    for (int i = 0; i < stiva.size(); ++i)
        inInfasuratoare[stiva[i]] = true;

    stiva.push_back(stiva[0]);

    for (int r = 1; r <= n; ++r)
    {
        if (inInfasuratoare[r])
            continue;

        double distMinim = INF;
        double raportMinim = INF;
        int pozInStiva = -1;

        for (int poz = 0; poz < (int)stiva.size() - 1; ++poz)
        {
            int i = stiva[poz];
            int j = stiva[poz + 1];

            if (dist[i][r] + dist[r][j] - dist[i][j] < distMinim)
            {
                distMinim = dist[i][r] + dist[r][j] - dist[i][j];
                raportMinim = (dist[i][r] + dist[r][j]) / dist[i][j];
                pozInStiva = poz;
            }
            else if (dist[i][r] + dist[r][j] - dist[i][j] == distMinim)
            {
                if ((dist[i][r] + dist[r][j]) / dist[i][j] < raportMinim)
                {
                    raportMinim = (dist[i][r] + dist[r][j]) / dist[i][j];
                    pozInStiva = poz;
                }
            }
        }

        stiva.push_back(-1);
        for (int i = (int)stiva.size() - 2; i >= pozInStiva + 1; --i)
            stiva[i + 1] = stiva[i];
        stiva[pozInStiva + 1] = r;

        inInfasuratoare[r] = true;
    }

    xMinim = INF;
    indexMinim = -1;
    for (int i = 0; i < stiva.size(); ++i)
    {
        if (pct[stiva[i]].first < xMinim)
        {
            xMinim = pct[stiva[i]].first;
            indexMinim = i;
        }
    }
    for (int i = indexMinim; i < stiva.size(); ++i)
        cout << pct[stiva[i]].first << ' ' << pct[stiva[i]].second << '\n';
    for (int i = 0; i < indexMinim; ++i)
        cout << pct[stiva[i]].first << ' ' << pct[stiva[i]].second << '\n';
    cout << '\n';
    */

    return 0;
}