Cod sursa(job #1796541)

Utilizator diana97Diana Ghinea diana97 Data 3 noiembrie 2016 16:23:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.91 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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


class Punct {
public:
    double x;
    double y;
    bool in_infasuratoare;
    
    Punct(double x, double y) {
        this->x = x;
        this->y = y;
        this->in_infasuratoare = false;
    }
    
    Punct() {
        this->x = this->y = 0;
        this->in_infasuratoare = false;
    }
    
    bool semn(Punct a, Punct b) {
        double semn = a.x * b.y + b.x * y + x * a.y - a.y * b.x - b.y * x - y * a.x;
        return semn < 0;
    }
    
    friend bool operator<(const Punct& p1, const Punct& p2);
    friend istream& operator>>(istream& is, Punct& p);
    friend ostream& operator<<(ostream& os, const Punct& p);
};

bool operator<(const Punct& p1, const Punct& p2) {
    if (p1.y == p2.y) return p1.x < p2.x;
    return p1.y < p2.y;
}

istream& operator>>(istream& is, Punct& p) {
    is >> p.x >> p.y;
    return is;
}

ostream& operator<<(ostream& os, Punct& p) {
    os << fixed << setprecision(6) << p.x << ' ' << p.y;
    return os;
}



class Figura {
private:
    vector <Punct> punct;
    vector <Punct> infasuratoare;

public:
    vector <Punct> get_infasuratoare() {
        if (infasuratoare.size() != 0) return infasuratoare;
        vector <int> stiva;
        int n = (int)punct.size();
        sort(punct.begin(), punct.end());
        
        stiva.push_back(0);
        punct[0].in_infasuratoare = false;
        
        stiva.push_back(1);
        punct[1].in_infasuratoare = false;
       
        int top = 1;
        int pas = 1;
        for (int i = 2; i >= 0; i+= pas) {
            if (i == n - 1) pas = -1;
            if (!punct[i].in_infasuratoare) {
                while(top >= 1 && punct[i].semn(punct[stiva[top - 1]], punct[stiva[top]])) {
                    punct[stiva[top]].in_infasuratoare = false;
                    stiva.pop_back();
                    top--;
                }
                top++;
                stiva.push_back(i);
                punct[i].in_infasuratoare = true;
            }
        }
        
        for (vector <int> :: iterator it = stiva.begin(); it != stiva.end(); it++) {
            infasuratoare.push_back(punct[*it]);
        }
        infasuratoare.pop_back();
        return infasuratoare;
    }

    friend istream& operator>>(istream& is, Figura& f);
};

istream& operator>>(istream& is, Figura& f) {
    int n;
    Punct p;
    
    is >> n;
    for (int i = 0; i < n; i++) {
        is >> p;
        f.punct.push_back(p);
    }
    f.get_infasuratoare();

    return is;
}

int main() {
    Figura figura;
    f >> figura;
    vector <Punct> infasuratoare = figura.get_infasuratoare();
    g << infasuratoare.size() << '\n';
    for (vector <Punct> :: iterator it = infasuratoare.begin(); it != infasuratoare.end(); it++) {
        g << *it << '\n';
    }
    g << '\n';
    return 0;
}