Cod sursa(job #3215935)

Utilizator andrei.eEnachescu Andrei andrei.e Data 15 martie 2024 14:39:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

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

struct punct
{
    double x, y, polar, dist;
    bool start;
}v[120005];

int left_turn (punct a, punct b, punct c)
{
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) >= 0;    
}

int n, start_y, start_x, indice;

bool criteriu (punct a, punct b)
{
    if (a.start)
        return 1;
    if (b.start)
        return 0;

    return a.polar < b.polar || (a.polar == b.polar && a.dist < b.dist);
}

int convex_hull[120005];

int main()
{
    in >> n;

    start_y = 1e9 + 1;
    for (int i = 1; i <= n; i ++)
    {
        in >> v[i].x >> v[i].y;

        if (v[i].y < start_y || (v[i].y == start_y && v[i].x > start_x))
        {
            start_x = v[i].x;
            start_y = v[i].y;
            indice = i;
        }

        v[i].start = false;
    }

    v[indice].start = true;

    for (int i = 1; i <= n; i ++)
        if (v[i].start == false)
        {
            v[i].dist = sqrt((v[indice].x - v[i].x) * (v[indice].x - v[i].x) + (v[indice].y - v[i].y) * (v[indice].y - v[i].y));
            
            if (v[indice].y == v[i].y)
                v[i].polar = -2e9;
            else v[i].polar = -(v[i].x - v[indice].x) / (v[i].y - v[indice].y);
        }

    sort (v + 1, v + n + 1, criteriu);

    convex_hull[0] = 2;
    convex_hull[1] = 1;
    convex_hull[2] = 2;

    for (int i = 3; i <= n; i ++)
    {
        while (convex_hull[0] >= 2 && !left_turn(v[convex_hull[convex_hull[0] - 1]], v[convex_hull[convex_hull[0]]], v[i]))
            convex_hull[0] --;

        convex_hull[0] ++;
        convex_hull[convex_hull[0]] = i;
    }

    out << convex_hull[0] << '\n';

    for (int i = 1; i <= convex_hull[0]; i ++)
        out << setprecision(6) << fixed << v[convex_hull[i]].x << ' ' << setprecision(6) << fixed << v[convex_hull[i]].y << '\n';
    return 0;
}