Cod sursa(job #2495730)

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

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

struct Point {
    double x, y;
    Point(double a = 0, double b = 0): x(a), y(b) {}
};
vector<Point> p;

/// test whether a turn is left or not
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);
}

/// order points by y 
bool comparer(const Point& a, const Point& b) {
    return isLeft(p[0], a, b);
}

/// find the 2nd point in stack
Point secondInStack(stack<Point> &s) {
    Point p = s.top();
    s.pop();
    Point sec = s.top();
    s.push(p);
    return sec;
}

int main() {
    int n, i;
    float x, y;
    p.reserve(n * sizeof(Point));
    fin>>n;
      
    for(i = 0; i < n; i++) {
        fin>>x>>y;
        p.push_back(*(new Point(x, y)));
        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 the points
    sort(p.begin() + 1, p.end(), comparer);
    
    if(n < 3) {
        fout<<"Convex hull can not be determined";
        return 0;
    }

    /// push the first 3 points into a stack
    stack<Point> s;
    s.push(p[0]);
    s.push(p[1]);

    /// process the remaining points
    for(i = 2; i < n; i++) {    
        /// eliminate points until the first 2 points in the stack make
        /// a left turn (counterclockwise turn)
        while(!isLeft(secondInStack(s), s.top(), p[i]) && s.size() >= 2)
            s.pop();
        s.push(p[i]);
    }

    int k = s.size();
    fout<<s.size()<<endl;
    
    /// print points in trigonometrical order - reverse the stack
    vector<Point> convex_hull;
    while(!s.empty()) {
        convex_hull.push_back(s.top());
        s.pop();
    }

    for(i = k - 1; i >= 0; i--)
        fout<<fixed<<setprecision(6)<<convex_hull[i].x<<" "<<convex_hull[i].y<<endl;
    return 0;
}