Cod sursa(job #2484199)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 30 octombrie 2019 19:10:26
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <iomanip>
#include <utility>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>

const double EPS = 1e-12;

inline double
crossProduct(const std::pair <double, double>& a,
             const std::pair <double, double>& b,
             const std::pair <double, double>& c)
{
    return (b.first - a.first) * (c.second - a.second) -
        (c.first - a.first) * (b.second - a.second);
}

int main()
{
    int N;
    std::pair <double, double> pts[120005];
    int hull[120005];

    std::ifstream in("infasuratoare.in");
    std::ofstream out("infasuratoare.out");

    in >> N;

    bool visited[120005];

    for (int i = 0; i < N; i++)
    {
        double x, y;

        in >> x >> y;

        pts[i] = std::make_pair(x, y);
        visited[i] = false;
    }

    std::sort(pts, pts + N);
    
    hull[0] = 0;
    hull[1] = 1;

    int top = 1;

    visited[0] = true;
    visited[1] = true;
    for (int i = 2, k = 1; i > -1; i += k)
    {
        if (visited[i])
        {
            continue;
        }

        //std::cout << crossProduct(pts[hull[top - 1]], pts[hull[top]], pts[i]) << std::endl;
        //std::cout << pts[i].first << ' ' << pts[i].second << std::endl;
        /*for (int j = 0; j <= top; j++)
        {
            std::cout << '\t' << pts[hull[j]].first << ' ' << pts[hull[j]].second << std::endl;
        }*/

        while (top and crossProduct(pts[hull[top - 1]], pts[hull[top]], pts[i]) < EPS)
        {
            visited[hull[top--]] = false;
        }

        //std::cout << i << std::endl;
        hull[++top] = i;
        visited[i] = true;

        if (N - 1 == i)
        {
            k = -1;
        }
    }

    out << top + 1 << std::endl;
    out << std::setprecision(12);
    for (int i = 0; i <= top; i++)
    {
        out << pts[hull[i]].first << ' ' << pts[hull[i]].second << std::endl;
    }

    return 0;
}