Cod sursa(job #2119952)

Utilizator tanasaradutanasaradu tanasaradu Data 1 februarie 2018 19:40:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int Nmax = 120005;
int n, st[Nmax], top;
struct P
{
    double ox, oy;
};
P a[Nmax];
bool viz[Nmax]; /// viz[i] = true => punctul i se afla in infasuratorare convexa


/// Sortez crescator dupa coordonata oy  si in caz de egalitate crescator dupa coordonata ox
inline bool CMP(const P A, const P B)
{
    if(A . oy == B . oy)
        return A . ox < B . ox;
    return A . oy < B . oy;
}
/// verific in ce cadran se afla punctul cu numarul k fata de dreapta determinata de punctele cu numarul i respectiv j
/// 0 = sunt coliniatre , > 0 se afla in cadranul + , < 0 se afla in cadranul -
inline double CHECK(int i, int j, int k)
{
    return (a[i] . ox * a[j] . oy + a[i] . oy * a[k] . ox + a[j] . ox * a[k] . oy
            - a[k] . ox * a[j] . oy - a[j] . ox * a[i] . oy - a[i] . ox * a[k] . oy);
}
inline void Solve()
{
    ++top;
    st[top] = 1;
    ++top;
    st[top] = 2;
    viz[top] = 2;
    for(int i = 3 ; i <= n ; i++)
    {
        while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
        {
            viz[st[top]] = false;
            top--;
        }
        ++top;
        st[top] = i;
        viz[i] = true;
    }
    for(int i = n ; i >= 1 ; i--)
        if(!viz[i]) /// nu se afla in infasuratoare
        {
            while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
            {
                viz[st[top]] = false;
                top--;
            }
            ++top;
            st[top] = i;
            viz[i] = true;
        }
    fout << (top - 1) << "\n";
    for(int i = 1 ; i < top ; i++)
        fout << fixed << setprecision(12) << a[st[i]] . ox << " " << a[st[i]] . oy << "\n";
}
int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; i++)
        fin >> a[i] . ox >> a[i] . oy;
    sort(a + 1, a + n + 1, CMP);
    Solve();
    fin.close();
    fout.close();
    return 0;
}