Cod sursa(job #2919000)

Utilizator Andrei_ierdnANeculau Rares-Andrei Andrei_ierdnA Data 14 august 2022 19:31:43
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n, i, n2, p1[120100], p2[120100], l1, l2;
pair<double, double> coord[120100];
const double eps = 0.000000000001;
double tg1, tg2;

bool ccw(int i1, int i2, int i3)
{
    if (abs(coord[i1].first - coord[i2].first) <= eps)
    {
        if (abs(coord[i3].first - coord[i2].first) <= eps)
            return false;
        if (coord[i1].second < coord[i2].second + eps) {
            if (coord[i3].first < coord[i1].first + eps)
                return true;
            return false;
        }
        if (coord[i3].first + eps > coord[i1].first)
            return true;
        return false;
    }
    if (abs(coord[i2].first - coord[i3].first) <= eps)
    {
        if (coord[i2].second < coord[i3].second + eps) {
            if (coord[i1].first < coord[i2].first + eps)
                return true;
            return false;
        }
        if (coord[i1].first + eps > coord[i2].first)
            return true;
        return false;
    }
    tg1 = (coord[i2].second - coord[i1].second);
    tg1 = tg1 / (coord[i2].first - coord[i1].first);
    tg2 = (coord[i3].second - coord[i1].second);
    tg2 = tg2 / (coord[i3].first - coord[i1].first);
    if (tg2 + eps > tg1)
        return true;
    return false;
}

int main()
{
    f >> n;
    for (i = 1; i <= n; i++)
        f >> coord[i].first >> coord[i].second;
    sort(coord+1, coord+n+1);
    n2 = n;
    for (i = 2; i <= n; i++)
    {
        if (coord[i].first == coord[i-1].first && coord[i].second == coord[i-1].second)
        {
            coord[i].first = coord[i].second = 1000000001;
            n2--;
        }
    }
    sort(coord+1, coord+n+1);
    n = n2;
    l1 = l2 = 0;
    if (n == 1)
        g << 1 << '\n' << coord[1].first << ' ' << coord[1].second;
    else if (n == 2)
        g << 2 << '\n' << coord[1].first << ' ' << coord[1].second << '\n' << coord[2].first << ' ' << coord[2].second;
    else
    {
        for (i = 1; i <= n; i++)
        {
            while (l1 >= 2 && !ccw(p1[l1-1], p1[l1], i))
                p1[l1--] = 0;
            p1[++l1] = i;
        }
        for (i = n; i >= 1; i--)
        {
            while (l2 >= 2 && !ccw(p2[l2-1], p2[l2], i))
                p2[l2--] = 0;
            p2[++l2] = i;
        }
        p1[l1--] = 0;
        p2[l2--] = 0;
        g << l1+l2 << '\n';
        for (i = 1; i <= l1; i++)
            g << coord[p1[i]].first << ' ' << coord[p1[i]].second << '\n';
        for (i = 1; i <= l2; i++)
            g << coord[p2[i]].first << ' ' << coord[p2[i]].second << '\n';
    }
    f.close();
    g.close();
    return 0;
}