Cod sursa(job #2119643)

Utilizator tanasaradutanasaradu tanasaradu Data 1 februarie 2018 14:53:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 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(P A , 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[k] . ox * (a[i] . oy - a[j] . oy) + a[k] . ox * (a[j] . ox - a[i] . ox)
            + a[i] . ox * a[j] . oy - a[j] . ox * a[i] . oy;
}
inline void Solve()
{
    ++top;
    st[top] = 1;
    viz[top] = true;
    ++top;
    st[top] = 2;
    viz[top] = true;
    for(int i = 3 ; i <= n ; i++)
        if(!viz[i]) /// verific daca nu se afla in infasuratoare
    {
        if(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])
    {
        if(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(6) << 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;
}