Cod sursa(job #2556583)

Utilizator alex02Grigore Alexandru alex02 Data 25 februarie 2020 00:28:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;

struct point {
    double x, y;
} puncte[120004];


bool compare(point x, point y) {
    return x.x < y.x;
}

void citire() {
    f >> n;
    for (int i = 0; i < n; ++i) {
        f >> puncte[i].x >> puncte[i].y;
    }
}

void afis(point a) {
    g<< a.x << " " << a.y << '\n';
}

bool sens_trigo(point A, point B, point C) {
    double det = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
    return det > 0;
}

void rezolvare() {
    vector<point> rez1, rez2;
    int nr1 = 2, nr2 = 2;

    rez1.push_back(puncte[0]);
    rez1.push_back(puncte[1]);
    for (int i = 2; i < n; i++) {
        while (nr1 > 1 && !sens_trigo(rez1[nr1 - 2], rez1[nr1 - 1], puncte[i])) {
            nr1--;
            rez1.pop_back();
        }
        rez1.push_back(puncte[i]);
        nr1++;
    }
    rez2.push_back(puncte[n - 1]);
    rez2.push_back(puncte[n - 2]);
    for (int i = n - 3; i >= 0; i--) {
        while (nr2 > 1 && !sens_trigo(rez2[nr2 - 2], rez2[nr2 - 1], puncte[i])) {
            nr2--;
            rez2.pop_back();
        }
        rez2.push_back(puncte[i]);
        nr2++;
    }
    rez1.pop_back();
    rez2.pop_back();

    g << nr1 + nr2 - 2 << endl;
    g<<setprecision(13)<<fixed;
    for (int i = 0; i < nr1 - 1; i++) {
        afis(rez1[i]);
    }
    for (int i = 0; i < nr2 - 1; i++) {
        afis(rez2[i]);
    }
}

int main() {
    citire();
    sort(puncte, puncte + n, compare);
    rezolvare();
    return 0;
}