Cod sursa(job #3215096)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 14 martie 2024 17:58:43
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Punct
{
    double l , c;
    double up;
}a[120001] , st[120001];

int N , k;

double Dist (Punct a , Punct b)
{
    int x = a.l - b.c , y = a.c - b.c;
    return sqrt (x * x + y * y);
}

bool fCmp (Punct A , Punct B)
{
    if(A.up != B.up)
        return A.up < B.up;
    else
    {
        if(A.c != B.c)
            return A.c < B.c;
        return A.l < B.l;
    }
}

int Det (Punct A , Punct B , Punct C)
{
    return A.l * (B.c - C.c) + B.l * (C.c - A.c) + C.l * (A.c - B.c);
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> a[i].l >> a[i].c;
    int p = 1;
    for (int i = 2; i <= N; ++i)
        if(a[i].c < a[p].c || (a[i].c == a[p].c && a[i].l < a[p].l))
            p = i;
    swap(a[p] , a[1]);
    for (int i = 2; i <= N; ++i)
        a[i].up = acos(1.0 * (a[i].l - a[1].l) / Dist (a[i] , a[1]));
    sort (a + 2 , a + N + 1 , fCmp);
    st[++k] = a[1];
    st[++k] = a[2];
    for (int i = 3; i <= N; ++i)
    {
        while(k >= 2 && Det (a[i] , st[k] , st[k - 1]) > 0)
            --k;
        st[++k] = a[i];
    }
    fout << k << "\n";
    for (int i = 1; i <= k; ++i)
        fout << fixed << setprecision(12) << st[i].l << " " << st[i].c << "\n";
}