Cod sursa(job #2496157)

Utilizator turtoieduardEduard Turtoi turtoieduard Data 20 noiembrie 2019 12:07:48
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>    
using namespace std;

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

//ifstream fin("input.in");
//ofstream fout("output.out");

struct Point {
    double x,y;
};
vector<Point> p;
stack<Point> s;

int isLeft(const Point &P, const Point &Q, const Point &R) {
    return ((Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x) > 0);
}
 
int comparer(const Point &P, const Point &Q) {
    return isLeft(p[0], P, Q);
}

Point nextInStack(stack<Point> s) {
    Point t = s.top();
    s.pop();
    Point sec = s.top();
    s.push(t);
    return sec;
}

int main() {
    int n, tp, i;
    fin>>n;
    p.resize(n);

    for(i = 0; i < n; i++)
        fin>>p[i].x>>p[i].y;
 
    for(i = 1; i < n; i++)
        if(p[0].x > p[i].x || (p[0].x == p[i].x && p[0].y > p[i].y))
            swap(p[0], p[i]);
 
    sort(p.begin() + 1, p.end(), comparer);
    
    s.push(p[0]);
    s.push(p[1]);
    for(int i = 2; i < n; i++) {
        while(s.size() >= 2 && !isLeft(nextInStack(s), s.top(), p[i]))
            s.pop();
        s.push(p[i]);
    }

    int k = s.size();
    vector<Point> convex_hull;

    while(!s.empty()) {
        convex_hull.push_back(s.top());
        s.pop();
    }

    fout<<k<<endl;
    for(int i = k - 1; i >= 0; i--)
        fout<<fixed<<setprecision(6)<<convex_hull[i].x<<' '<<convex_hull[i].y<<'\n';


}