Cod sursa(job #2866922)

Utilizator Florinos123Gaina Florin Florinos123 Data 10 martie 2022 08:46:02
Problema Rubarba Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

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

int n;

double aria;

int sol[100005], k;

struct point {
int x, y;
}v[100005];

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

    if (aux == 0) return 0;

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

    if (aux > 0) return 2;
}

int distanta (point a, point 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=1; i<n; i++)
        if (v[i].x < v[l].x)
           l = i;

    int a = l, b;

    do
    {
        k ++; sol[k] = a;

        b = (a + 1) % n;
        for (int i=0; i<n; i++)
        {
            if (Orientare(v[a], v[b], v[i]) == 2)
                b = i;
            else if (Orientare(v[a], v[b], v[i]) == 0)
            {
                if (distanta(v[a], v[b]) < distanta(v[a], v[i]))
                    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();

    k ++;
    sol[k] = sol[1];

    for (int i=1; i<=k; i++)
    {
        aria += (v[sol[i]].x * v[sol[i+1]].y);
        aria -= (v[sol[i]].y * v[sol[i+1]].x);
    }

    if (aria < 0) aria = -aria;

    aria /= 2.0;

    g << fixed << setprecision(2);
    g << aria;

    return 0;
}