Cod sursa(job #3226994)

Utilizator NeganAlex Mihalcea Negan Data 23 aprilie 2024 20:45:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;

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

struct Point {
    double x, y;
};

int n;
vector<Point> a;

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

bool cmp(Point A, Point B) {
    return getWay(a[0], A, B) > 0;
}

void Citire() {
    fin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++)
        fin >> a[i].x >> a[i].y;
}

void ConvexHull() {
    int minP = 0;
    for (int i = 1; i < n; i++)
        if (a[i].y < a[minP].y || (a[i].y == a[minP].y && a[i].x < a[minP].x))
            minP = i;
    swap(a[0], a[minP]);
    sort(a.begin() + 1, a.end(), cmp);

    vector<int> stv;
    stv.push_back(0);
    stv.push_back(1);
    for (int i = 2; i < n; i++) {
        while (stv.size() >= 2 && getWay(a[stv[stv.size() - 2]], a[stv.back()], a[i]) <= 0)
            stv.pop_back();
        stv.push_back(i);
    }

    fout << stv.size() << "\n";
    for (int i : stv)
        fout << setprecision(9) << fixed << a[i].x << " " << a[i].y << "\n";
}

int main() {
    Citire();
    ConvexHull();
    return 0;
}