Cod sursa(job #2503364)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 2 decembrie 2019 22:11:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

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

struct punct {
    double x, y;
    void print_punct() {
        out << x << ' ' << y << '\n';
    }
    bool operator==(const punct& B) {
        if (abs(x - B.x) < 0.000001 && abs(y - B.y) < 0.000001)
            return true;
        return false;
    }
};
 
bool cmp(punct& A, punct& B) {
    if (A.x < B.x)
        return true;
    if (A.x > B.x)
        return false;
    if (A.y < B.y)
        return true;
    return false;
}
 
bool viraj(vector <punct>& stiva) {
    int n = stiva.size();
    double x1 = stiva[n - 3].x, y1 = stiva[n - 3].y;
    double x2 = stiva[n - 2].x, y2 = stiva[n - 2].y;
    double x3 = stiva[n - 1].x, y3 = stiva[n - 1].y;
    double det = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
    if (det > 0)
        return true;
    return false;
}
 
int main() {
    int n;
    in >> n;
    vector <punct> A(n);
    
    for (int i = 0; i < n; i++) {
        in >> A[i].x >> A[i].y;
    }
 
    sort(A.begin(), A.end(), cmp);
    punct st = A[0], dr = A[n - 1];
    vector <punct> stiva;
    stiva.push_back(A[0]);
    stiva.push_back(A[1]);
 
    for (int i = 2; i < n; i++) {
        stiva.push_back(A[i]);
        while (stiva.size() > 2 && !viraj(stiva)) {
            stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
            stiva.pop_back();
        }
    }
 
    vector <punct> sol = stiva;
    stiva.clear();
    stiva.push_back(A[n - 1]);
    stiva.push_back(A[n - 2]);
    for (int i = n - 3; i >= 0; i--) {
        stiva.push_back(A[i]);
        while (stiva.size() > 2 && !viraj(stiva)) {
            stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
            stiva.pop_back();
        }
    }
 
    for (int i = 1; i < stiva.size() - 1; i++)
            sol.push_back(stiva[i]);
 
    out << fixed << setprecision(12);
    out << sol.size() << '\n';
    for (auto &&el: sol) {
        el.print_punct();
    }
 
    return 0;
}