Cod sursa(job #2378938)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 12 martie 2019 19:18:09
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;
struct punct
{
    long double x, y;
}v[120005], sol[120005], val1, val2;
bool cmp(punct a, punct b)
{
    return a.y < b.y;
}
int i, j, n, k;
bool ok, seen[120005];
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f >> n;
    for(i = 1; i <= n; i ++)
        f >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    sol[++k] = v[1];
    seen[1] = true;
    do
    {
        for(i = 1; i <= n; i ++)
            if(seen[i] == false)
            {
                ok = true;
                val1.x = sol[k].x - v[i].x;
                val1.y = sol[k].y - v[i].y;
                for(j = 1; j <= n; j ++)
                    if(seen[j] == false && i != j)
                    {
                        val2.x = sol[k].x - v[j].x;
                        val2.y = sol[k].y - v[j].y;
                        if(val1.x * val2.y - val2.x * val1.y > 0)
                        {
                            ok = false;
                            break;
                        }
                    }
                if(ok == true)
                {
                    sol[++k] = v[i];
                    seen[i] = true;
                    break;
                }
            }
        seen[1] = false;
    }
    while(sol[k].x != sol[1].x || sol[k].y != sol[1].y);
    g << k - 1 << "\n";
    reverse(sol + 1, sol + k + 1);
    for(i = 1; i < k; i ++)
        g << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}