Cod sursa(job #2640421)

Utilizator mihai03Mihai Grigore mihai03 Data 6 august 2020 13:31:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <tgmath.h>
#include <iomanip>
#include <iostream>
using namespace std;

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

struct Punct
{
    long double x, y;
    long double unghi_polar;
};

int n;

vector < Punct > v;

int vf;
Punct s[120001];

void PUSH(Punct P)
{
    ++vf;
    s[vf] = P;
}

void POP()
{
    vf--;
}

bool sortare(Punct A, Punct B)
{
    if(A.unghi_polar > B.unghi_polar) return false;
    if(A.unghi_polar == B.unghi_polar)
    {
        if(A.y > B.y) return false;
    }
    return true;
}

long double ceas_trig(Punct A, Punct B, Punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int main()
{
    fin >> n;

    Punct p;

    for(int i = 1; i <= n; i++)
    {
        fin >> p.x >> p.y;
        v.push_back(p);
        // cout << v[i - 1].x << " " << v[i - 1].y << "\n";
    }

    Punct punct_minim;

    punct_minim = v[0];
    for(int i = 1; i < n; i++)
    {
        if(v[i].y < punct_minim.y)
        {
            punct_minim = v[i];
        }
        else if(v[i].y == punct_minim.y)
        {
            if(v[i].x < punct_minim.x) punct_minim = v[i];
        }
    }

    for(int i = 0; i < n; i++)
    {
        v[i].unghi_polar = atan2(v[i].y - punct_minim.y, v[i].x - punct_minim.x);
    }

    sort(v.begin(), v.end(), sortare);

    PUSH(v[0]);
    PUSH(v[1]);

    for(int i = 2; i < n; i++)
    {
        long double o = ceas_trig(s[vf - 1], s[vf], v[i]);

        if(o == 0)
        {
            POP();
            PUSH(v[i]);
        }
        else
        {
            if(o > 0)
            {
                PUSH(v[i]);
            }
            else
            {
                while(o <= 0 && vf > 1)
                {
                    POP();
                    o = ceas_trig(s[vf - 1], s[vf], v[i]);
                }
                PUSH(v[i]);
            }
        }
    }

    fout << vf << "\n";
    for(int i = 1; i <= vf; i++)
    {
        fout << fixed << setprecision(6) << s[i].x << " " << s[i].y << "\n";
    }

    return 0;
}