Cod sursa(job #2535660)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 1 februarie 2020 10:22:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct punct{
    double x, y;
    punct(double cx = 0, double cy = 0){
        this->x = cx;
        this->y = cy;
    }

    bool operator<(const punct &other) const {
        if(this->x == other.x){
            return this->y < other.y;
        }
        return this->x < other.x;
    }
};

int n;
vector<pair<punct, bool>> puncte;

bool intoarcere(punct a, punct b, punct c){
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) >= 0;
}

void citire(){
    ifstream f("infasuratoare.in");
    f>>n;
    for (int i = 0; i < n; ++i) {
        puncte.emplace_back();
        f>>puncte[i].first.x>>puncte[i].first.y;
        puncte[i].second = false;
    }
}

vector<int> build(){
    vector<int> result;
    result.push_back(0);
    result.push_back(1);
    puncte[1].second = true;
    for (int i = 2; i < n; ++i) {
        while(result.size() >= 2 && !intoarcere(puncte[result[result.size() - 2]].first, puncte[result[result.size() - 1]].first, puncte[i].first)){
            puncte[result[result.size() - 1]].second = false;
            result.pop_back();
        }
        result.push_back(i);
        puncte[i].second = true;
    }
    for(int i = n - 2; i >= 0; i--){
        if(puncte[i].second)
            continue;
        while(result.size() >= 2 && !intoarcere(puncte[result[result.size() - 2]].first, puncte[result[result.size() - 1]].first, puncte[i].first)){
            puncte[result[result.size() - 1]].second = false;
            result.pop_back();
        }
        result.push_back(i);
        puncte[i].second = true;
    }
    result.pop_back();
    return result;
}

int main() {
    citire();
    sort(puncte.begin(), puncte.end());
    vector<int> result = build();
    ofstream g("infasuratoare.out");
    g<<result.size()<<"\n";
    g<<setprecision(6)<<fixed;
    for (auto & i : result) {
        g<<puncte[i].first.x<<' '<<puncte[i].first.y<<"\n";
    }
    return 0;
}