Cod sursa(job #2659644)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 17 octombrie 2020 11:38:29
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct point{
    double x, y;
    point(double x, double y){
        this->x = x;
        this->y = y;
    }
    bool operator<(const point &other) const {
        if(this->x < other.x)
            return true;
        else if(this->x == other.x)
            return this->y < other.y;
        else return false;
    }
    bool operator!= (const point &other) const {
        if(this->x == other.x && this->y == other.y)
            return false;
        return true;
    }
};

double determinant(point a, point b, point c){
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}


int main() {
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n;
    f>>n;
    vector<point> p;
    for (int i = 0; i < n; ++i) {
        double x, y;
        f>>x>>y;
        p.emplace_back(x, y);
    }
    sort(p.begin(), p.end());
    vector<point> v1;
    v1.push_back(p[0]);
    v1.push_back(p[1]);
    for (int i = 2; i < n; ++i) {
        if(v1.size() > 1){
            if(determinant(v1[v1.size() - 2], v1[v1.size() - 1], p[i]) >= 0){
                v1.push_back(p[i]);
            }else{
                v1.pop_back();
                i--;
            }
        }else v1.push_back(p[i]);
    }
    reverse(p.begin(), p.end());
    vector<point> v2;
    v2.push_back(p[0]);
    v2.push_back(p[1]);
    for (int i = 2; i < n; ++i) {
        if(v2.size() > 1){
            if(determinant(v2[v2.size() - 2], v2[v2.size() - 1], p[i]) >= 0){
                v2.push_back(p[i]);
            }else{
                v2.pop_back();
                i--;
            }
        }else v2.push_back(p[i]);
    }
    g<<v1.size() + v2.size() - 2<<"\n";
    for (int i = 0; i < v1.size(); ++i) {
        g<<v1[i].x<<' '<<v1[i].y<<'\n';
    }
    for (int i = 1; i < v2.size() - 1; ++i) {
        g<<v2[i].x<<' '<<v2[i].y<<'\n';
    }
    return 0;
}