Cod sursa(job #2690437)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 23 decembrie 2020 22:40:34
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const int NMAX = 120000;

pair<double, double> vec[1 + NMAX];

int vf;
int stiva[1 + NMAX];

const double EPS = 0.0000000000001;

bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
    return atan2(b.second - vec[1].second, b.first - vec[1].first) - atan2(a.second - vec[1].second, a.first - vec[1].first) > EPS;
}

inline double ccw(const pair<double, double>& o, const pair<double, double>& a, const pair<double, double>& b) /// B fata de vectorul OA(orientat de la O la A), e + pt stanga, - pt dreapta, 0 daca e pe OA
{
    return (o.first - a.first) * (b.second - a.second) - (o.second - a.second) * (b.first - a.first);
}

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

    double minimX = 1000000001.0;
    double minimY = 1000000001.0;
    int index = -1;


    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> vec[i].first >> vec[i].second;
        if (vec[i].first < minimX)
        {
            minimX = vec[i].first;
            minimY = vec[i].second;
            index = i;
        }
        else if (vec[i].first == minimX)
        {
            if (vec[i].second < minimY)
            {
                minimY = vec[i].second;
                index = i;
            }
        }
    }

    swap(vec[1], vec[index]);
    vf++;
    stiva[vf] = 1;

    sort(vec + 1 + 1, vec + 1 + n, comp);

    for (int i = 2; i <= n; i++)
    {
        while (vf >= 2 && ccw(vec[stiva[vf - 1]], vec[stiva[vf]], vec[i]) > 0.0)
        {
            vf--;
        }
        vf++;
        stiva[vf] = i;
    }

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

    return 0;
}