Cod sursa(job #2957004)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 21 decembrie 2022 15:39:23
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 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> v;

bool comp(point A, point B) {
    if((A.y - v[0].y) * (B.x - A.x) <= (B.y - A.y) * (A.x - v[0].x))
        return true;

    return false;
}

bool ok(point A, point B, point C) {
    if((B.y - A.y) * (C.x - B.x) <= (C.y - B.y) * (B.x - A.x))
        return true;

    return false;
}

int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++) {
        double x, y;

        fin >> x >> y;

        v.push_back({x, y});
    }

    // aflam care e P (punctul de plecare)

    int idxP = 0;
    double minX = 2000000000, minY = 2000000000;

    for(int i = 0; i < v.size(); i++)
        if(minX > v[i].x || (minX == v[i].x && minY > v[i].y)) {
            minX = v[i].x;
            minY = v[i].y;

            idxP = i;
        }

    swap(v[0], v[idxP]);

    // sortam restul punctelor dupa unghiul pe care il formeaza cu P

    sort(&v[1], &v[v.size()], comp);

    vector<point> stk;

    stk.push_back(v[0]);
    stk.push_back(v[1]);

    for(int i = 2; i < v.size(); i++) {
        while(!ok(stk[stk.size() - 2], stk[stk.size() - 1], v[i])) {
            stk.pop_back();
        }

        stk.push_back(v[i]);
    }

    fout << stk.size() << '\n';

    for(int i = 0; i < stk.size(); i++)
        fout << fixed << setprecision(6) << stk[i].x << ' ' << stk[i].y << '\n';

    return 0;
}