Cod sursa(job #2998821)

Utilizator AlexCroitoriuAlex Croitoriu AlexCroitoriu Data 10 martie 2023 09:17:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>

using namespace std;
fstream f("infasuratoare.in", ios::in), g("infasuratoare.out", ios::out);
struct point
{
    double x, y;
} v[120001];    
vector<point> s;
inline double relative(point a, point b, point c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline bool cmp(point a, point b)
{
    return relative(v[1], a, b) < 0;
}
int main()
{
    int n;
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i].x >> v[i].y;
    int m = 1;
    for (int i = 2; i <= n; i++)
        if (v[i].x < v[m].x || (v[i].x == v[m].x && v[i].y < v[m].y))
            m = i;
    swap(v[1], v[m]);
    sort(v + 2, v + n + 1, cmp);
    s.push_back(v[1]);
    s.push_back(v[2]);
    for (int i = 3; i <= n; i++)
    {
        while (s.size() >= 2 && relative(s[s.size() - 2], s[s.size() - 1], v[i]) > 0)
            s.pop_back();
        s.push_back(v[i]);
    }
    g << s.size() << '\n';
    for (auto rit = s.rbegin(); rit != s.rend(); rit++)
        g << fixed << setprecision(6) << rit->x << ' ' << rit->y << '\n';
}