Cod sursa(job #2835642)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 19 ianuarie 2022 00:06:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 120000;

int N;
struct elem
{
    long double x, y;
};
elem punct[NMAX + 5];
elem stiva[NMAX + 5];
int cntStiva;

long double determinant(elem a, elem b, elem c)
{
    return (a.x * b.y - a.y * b.x) + (b.x * c.y - b.y * c.x) + (c.x * a.y - a.x * c.y);
}

bool verifica(elem a, elem b, elem c)
{
    return (determinant(a, b, c) > 0);
}

bool cmp(elem a, elem b)
{
    return verifica(punct[1], a, b);
}

int main()
{
    fin >> N;
    for(int i = 1; i <= N; i ++)
    {
        fin >> punct[i].x >> punct[i].y;
    }
    for(int i = 2; i <= N; i ++)
    {
        if(punct[1].y > punct[i].y)
        {
            swap(punct[1], punct[i]);
        }
        else
        {
            if(punct[1].y == punct[i].y)
            {
                if(punct[1].x > punct[i].x)
                {
                    swap(punct[1], punct[i]);
                }
            }
        }
    }
    sort(punct + 2, punct + N + 1, cmp);
    stiva[++cntStiva] = punct[1];
    for(int i = 2; i <= N; i ++)
    {
        while(cntStiva >= 2 && verifica(stiva[cntStiva - 1], stiva[cntStiva], punct[i]) == false)
        {
            cntStiva--;
        }
        stiva[++cntStiva] = punct[i];
    }
    fout << cntStiva << '\n';
    for(int i = 1; i <= cntStiva; i ++)
    {
        fout << fixed << setprecision(12) << stiva[i].x << ' ';
        fout << fixed << setprecision(12) << stiva[i].y << ' ';
        fout << '\n';
    }
    return 0;
}