Cod sursa(job #2551525)

Utilizator alex02Grigore Alexandru alex02 Data 19 februarie 2020 21:44:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <queue>

using namespace std;

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

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

queue<point> Q;

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 << setprecision(13) << fixed << a.x << " " << a.y << endl;
}

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() {
    point A, B;
    int nr=0;
    A = puncte[0], B = puncte[1];
    //Q.push(A);
    for (int i = 2; i < n; i++) {
        if (!sens_trigo(A, B, puncte[i])) {
            B = puncte[i];
        } else {
            Q.push(B);
            nr++;
            A = B;
            B = puncte[i];
        }
    }
    if (sens_trigo(A, B, puncte[n-1])) {
        Q.push(B);
        nr++;
        A = B;
        B = puncte[n-1];
    }
    A=puncte[n-1], B=puncte[n-2];
    for (int i = n-3; i >=0; i--) {
        if (!sens_trigo(A, B, puncte[i])) {
            B = puncte[i];
        } else {
            Q.push(B);
            nr++;
            A = B;
            B = puncte[i];
        }
    }
    if (sens_trigo(A, B, puncte[0])) {
        Q.push(B);
        nr++;
        A = B;
        B = puncte[0];
    }
    g<<nr<<endl;
    while(!Q.empty()){
        afis(Q.front());
        Q.pop();
    }
}


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

    return 0;
}