Cod sursa(job #2544021)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 11 februarie 2020 18:25:54
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#define INF 1000000001
using namespace std;
int n, i, k;
bool ok;
struct dot
{
    double x, y;
}v[120005], minn, sol[120005];
bool lefter(dot a, dot b, dot c)
{
    double x1 = a.x - b.x;
    double x2 = a.x - c.x;
    double y1 = a.y - b.y;
    double y2 = a.y - c.y;
    double rez = y2 * x1 - y1 * x2;
    if(rez > 0)return true;
    return false;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f >> n;
    minn.y = INF;
    minn.x = INF;
    for(i = 1; i <= n; i ++)
    {
        f >> v[i].x >> v[i].y;
        if(v[i].y < minn.y)minn = v[i];
        else if(v[i].y == minn.y && v[i].x < minn.x)minn = v[i];
    }
    sol[1] = minn;
    k = 1;
    do
    {
        ok = false;
        for(i = 1; i <= n; i ++)
        {
            if(v[i].x == sol[k].x && v[i].y == sol[k].y)continue;
            if(ok == false)
            {
                sol[ ++k] = v[i];
                ok = true;
                continue;
            }
            if(lefter(sol[k - 1], sol[k], v[i]))sol[k] = v[i];
        }
    }
    while(sol[1].x != sol[k].x || sol[1].y != sol[k].y);
    g << k - 1 << "\n";
    for(i = k; i > 1; i --)
        g << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}