Cod sursa(job #2501009)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 28 noiembrie 2019 22:36:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define N_MAX 120005

using namespace std;

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

int n, k1, k2, j = 1;
int stiva1[N_MAX], stiva2[N_MAX];
pair < double, double > v[N_MAX];
vector < int > ans;

bool Elim(int *stiva, int k, int pos)
{
    pair < double, double > A = v[stiva[k - 1]], B = v[stiva[k]], C = v[pos];
    return (((B.x - C.x) * (C.y - A.y) - (B.y - C.y) * (C.x - A.x)) < 0);
}

void ConvexHull(int *stiva, int &k)
{
    stiva[++k] = 1;
    stiva[++k] = 2;
    for (int i = 3; i <= n; i++)
    {
        while (k > 1 && Elim(stiva, k, i))
            k--;
        stiva[++k] = i;
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1);

    ConvexHull(stiva1, k1);
    reverse(v + 1, v + n + 1);
    ConvexHull(stiva2, k2);

    for (int i = 1; ((n - stiva1[i] + 1) != stiva2[1]) && (i <= k1); i++)
    {
        ans.push_back(n - stiva1[i] + 1);
        if (n - stiva1[i] + 1 == stiva2[k2])
            k2--;
    }
    for (int i = j; i <= k2; i++)
        ans.push_back(stiva2[i]);

    fout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        fout << fixed << setprecision(6) << v[ans[i]].x << " " << v[ans[i]].y << "\n";
    return 0;
}