Cod sursa(job #2976903)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 10 februarie 2023 12:28:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

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


struct Punct {
    long double x, y;
    bool operator < (const Punct A) const {
        if (y == A.y)
            return x < A.x;
        return y < A.y;
    }
};

long double Calc (Punct A, Punct B, Punct C) {
    long double a = B.y - A.y;
    long double b = A.x - B.x;
    long double c = A.x * (A.y - B.y)+ A.y * (B.x - A.x);
    return a * C.x + b * C.y + c;
}

const int MaxN = 120005;

int n, st[MaxN], top, viz[MaxN], cnt;
Punct a[MaxN];
vector <Punct> sol;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1);
    st[1] = 1;
    sol.push_back(a[1]);
    top = 1;
    for (int i = 2; i <= n; i++) {
        while (top >= 2 && Calc(a[st[top - 1]], a[st[top]], a[i]) > 0)  {
            viz[st[top]] = 0;
            sol.pop_back();
            top--;
        }
        viz[i] = 1;
        st[++top] = i;
        sol.push_back(a[i]);
    }
    top = 1;
    st[1] = n;
    for (int i = n - 1; i > 0; i--) if (!viz[i]) {
         while (top >= 2 && Calc(a[st[top - 1]], a[st[top]], a[i]) > 0)  {
            viz[st[top]] = 0;
            sol.pop_back();
            top--;
        }
        viz[i] = 1;
        st[++top] = i;
        if (i != 1)
            sol.push_back(a[i]);
    }
    fout << sol.size() << "\n";
    for (auto i : sol)
        fout << fixed << setprecision(12) << i.x << " " << i.y << "\n";

    return 0;
}