Cod sursa(job #3222759)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 11 aprilie 2024 16:23:25
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;
using point=pair<double,double>;

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

const int MAXN = 12e4;
const double SHIFT= 1e9;
point v[MAXN];
point *O = v;

bool cmp(point &A, point &B) {
    return (A.second - O->second)*(B.first - O->first) < (A.first - O->first)*(B.second - O->second);
}

bool cmp2(point &A, point &B) {
    if (A.second == B.second)
        return A.first < B.first;
    return A.second < B.second;
}

point shift(point A) {
    return {A.first + SHIFT, A.second + SHIFT};
}

double cmpcrossProduct(point A, point B) {
    A = shift(A);
    B = shift(B);
    return A.first * B.second > A.second * B.first;
}

double crossProduct(point A, point B) {
    return A.first * B.second > A.second * B.first;
}

bool trigonometricOrder(point A, point B, point C) {
    // Calculam vectorii AB si BC
    point AB = {B.first - A.first, B.second - A.second};
    point BC = {C.first - B.first, C.second - B.second};

    // Determinam produsul vectorial al acestor vectori
    double cross = crossProduct(AB, BC);

    // Verificam semnul produsului vectorial pentru a stabili ordinea trigonometrica
    return cross > 0;
}

int main() {
    int n;
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i].first >> v[i].second;
    sort(v, v + n, cmp2);
    sort(v + 1, v + n, cmp);
    vector<point> poli;
    poli.push_back(*O);
    poli.push_back(v[1]);
    for (int i = 2; i < n - 1; i++) {
        while (i < n - 1 && !trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
            i++;
        poli.push_back(v[i]);
        if (i == n - 2)
            poli.push_back(v[n - 1]);
    }
    //sort(poli.begin(), poli.end(), crossProduct);
    fout << poli.size() << '\n';
    for (point elem: poli)
        fout << fixed << setprecision(14) << elem.first << ' ' << elem.second << '\n';

    return 0;
}