Cod sursa(job #2866714)

Utilizator Florinos123Gaina Florin Florinos123 Data 9 martie 2022 21:52:39
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

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

struct punct {
double x, y;
};

int n;

vector < int > sol;

punct v[120005];

int Orientare (punct a, punct b, punct c)
{
    int aux = (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);

    if (aux == 0) return 0; // a, b, c - coliniare

    if (aux < 0) return 1; // c - este la stanga segmentului [a,b]

    if (aux > 0) return 2; // c - este la dreapta segmentului [a,b]
}

int dist (punct a, punct b)
{
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y); // distanta la patrat dintre 2 puncte
}

void Infasuratoare ()
{
    int l = 0;
    for (int i=0; i<n; i++)  // cautam cel mai din stanga punct care sigur se afla pe infasuratoare
        if (v[l].x > v[i].x)
            l = i;

    int a = l, b, c;

    do
    {
        sol.push_back(a); // adaugam punctul curent la solutie

        b = (a + 1) % n; // presupunem ca urmatorul punct e pe infasuratoare
        for (int i=0; i<n; i++)
        {
            if (Orientare(v[a], v[b], v[i]) == 2) // daca gasim un punct la dreapta lui [a,b] actualizam solutia
                b = i;
            else if (Orientare(v[a], v[b], v[i]) == 0)  // daca punctele sunt coliniare il alegem pe cel mai indepartat
            {
                if (dist(v[a], v[i]) > dist(v[a], v[b]))
                    b = i;
            }
        }

        a = b; // cel mai bun punct gasit il pregatim pentru iterarea urmatoare

    } while (a != l); // repetam pana ajungem de unde am plecat
}

int main()
{
    f >> n;
    for (int i=0; i<n; i++)
        f >> v[i].x >> v[i].y;

   Infasuratoare();

   g << sol.size() << "\n";
   for (int i=0; i<sol.size(); i++)
   {
       g << fixed << setprecision(6);
       g << v[sol[i]].x << " " << v[sol[i]].y << "\n";
   }
    return 0;
}