Cod sursa(job #2866705)

Utilizator Florinos123Gaina Florin Florinos123 Data 9 martie 2022 21:50:05
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 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; // 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);
}

void Infasuratoare ()
{
    int l = 0;
    for (int i=0; i<n; i++)
        if (v[l].x > v[i].x)
            l = i;

    int a = l, b, c;

    do
    {
        sol.push_back(a);

        b = (a + 1) % n;
        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)
            {
                if (dist(v[a], v[i]) > dist(v[a], v[b]))
                    b = i;
            }
        }

        a = b;

    } while (a != l);
}

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";
   }

  // g << fixed << setprecision(6);
   //g << v[sol[0]].x << " " << v[sol[0]].y << "\n";

    return 0;
}