Cod sursa(job #2720737)

Utilizator dimi999Dimitriu Andrei dimi999 Data 11 martie 2021 11:16:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

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

struct Points
{
    double x, y;

    bool operator < (const Points &other) const
    {
        if(x == other.x)
            return y < other.y;

        return x < other.x;
    }
};

int st[125000];

vector <Points> p;

bool viz[125000];

double Slopes(Points A, Points B, Points C)
{
    return (A.y - C.y) * (B.x - C.x) - (A.x - C.x) * (B.y - C.y);
}

int main()
{
    int N;

    fin >> N;

    for(int i = 1; i <= N; i++)
    {
        double x, y;

        fin >> x >> y;

        p.push_back({x, y});
    }

    sort(p.begin(), p.end());

    st[1] = 0;
    st[2] = 1;

    int top = 2;

    viz[1] = true;

    int pas = 1, poz = 1;

    while(!viz[0])
    {
        while(viz[poz] == true)
        {
            if(poz == N - 1)
                pas = -1;
            poz += pas;
        }

        while(Slopes(p[poz], p[st[top]], p[st[top - 1]]) > 0 && top >= 2)
            viz[st[top]] = false, top --;

        st[++top] = poz;
        viz[poz] = true;
    }

    top--;

    fout << top << '\n';

    for(int i = top; i >= 1; i--)
        fout << fixed << setprecision(12) << p[st[i]].x << " " << fixed << setprecision(12) << p[st[i]].y << '\n';

    return 0;
}