Cod sursa(job #2713057)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 27 februarie 2021 10:28:46
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;
/// Convex Hull - O(n log n)

/**
x * (B.y - A.y) + y*(A.x-B.x) + A.y*(B.x-A.x)+A.x*(B.y-A.y) = 0
*/
struct punct
{
    double x, y;
};
int st[103], n, top, viz[102];
punct a[102];

bool Cmp(punct A, punct B)
{
    if (A.y == B.y) return A.x < B.x;
    return A.y < B.y;
}

void Citire()
{
    ifstream fin("infasuratoare.in");
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
    fin.close();
}

int F(punct A, punct B, punct C)
{
    int rez = C.x * (B.y - A.y) + C.y * (A.x-B.x) +
       A.y*(B.x-A.x)-A.x*(B.y-A.y);
    if (rez < 0) return -1;
    if (rez > 0) return 1;
    return 0;
}

void Convex_Hull()
{
    int i;
    sort(a + 1, a + n + 1, Cmp);
    top = 0;
    st[++top] = 1;
    st[++top] = 2;
    viz[1] = viz[2] = 1;
    for (i = 3; i <= n; i++)
    {
        while (top >= 2 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
        {
            viz[ st[top] ] = 0;
            top--;
        }
        st[++top] = i;
        viz[i] = 1;
    }
    /// parcurgem punctele nevizitate de la n la 1
    viz[1] = 0;
    for (i = n; i >= 1; i--)
        if (viz[i] == 0)
        {
            while (top >= 2 && F(a[st[top-1]], a[st[top]], a[i]) > 0)
            {
                viz[ st[top] ] = 0;
                top--;
            }
            st[++top] = i;
            viz[i] = 1;
        }
    top--;
}

void Afisare()
{
    ofstream fout("infasuratoare.out");
    fout << top << "\n";
    for (int i = 1; i <= top; i++)
        fout << fixed << setprecision(12) << a[st[i]].x << " " << a[st[i]].y << "\n";
    fout.close();
}

int main()
{
    Citire();
    Convex_Hull();
    Afisare();
    return 0;
}