Cod sursa(job #2145525)

Utilizator tanasaradutanasaradu tanasaradu Data 27 februarie 2018 13:40:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int Nmax = 120005;
struct Point
{
    double x, y;
};
Point a[Nmax];
int st[Nmax], top, n;
bool viz[Nmax];
inline bool CMP(const Point A, const Point B)
{
    if(A . y == B . y)
        return A . x < B  . x;
    return A . y < B . y;
}
/// verific in ce cadran se afla punctul cu numarul k de dreapta determinata de punctele cu numarul i respectiv
/// j
inline bool CHECK(int i, int j, int k)
{
    return (a[i] . x * a[j] . y + a[i] . y * a[k] . x + a[j] . x * a[k] . y
            - a[j] . y * a[k] . x - a[j] . x * a[i] . y - a[k] . y * a[i] . x) < 0;
}
inline void HILL()
{
    ++top;
    st[top] = 1;
    ++top;
    st[top] = 2;
    viz[2] = true;
    for(int i = 3 ; i <= n ; i++)
    {
        while(top > 1 && CHECK(st[top - 1], st[top], i))
        {
            viz[st[top]] = false;
            top--;
        }
        ++top;
        st[top] = i;
        viz[i] = true;
    }
    /// inchid poligonul
    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))
            {
                viz[st[top]] = false;
                top--;
            }
            ++top;
            st[top] = i;
            viz[i] = true;
        }
    fout << top - 1 << "\n"; /// iau primul punct de doua ori(odata si cand inchid poligonul)
    for(int i = 1 ; i < top ; i++)
        fout << fixed << setprecision(6) << a[st[i]] . x << " " << a[st[i]] . y << "\n";
}
int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; i++)
        fin >> a[i] . x >> a[i] . y;
    sort(a + 1, a + n + 1, CMP);
    HILL();
    fin.close();
    fout.close();
    return 0;
}