Cod sursa(job #2495682)

Utilizator turtoieduardEduard Turtoi turtoieduard Data 19 noiembrie 2019 19:03:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.87 kb
#include <fstream>
#include <stack>
#include <vector>
#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) {}
} bottom;

double orientation_Test(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); 
    /// colinear points
    if(val == 0)  
        return 0;
    /// clockwise
    else if(val > 0)
        return -1;
    /// counterclockwise
    return 1;
}

double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

/// sort counteclockwise to bottom and by distance if equal angle
bool comparer(const Point& a, const Point& b) {
    int o = orientation_Test(bottom, a, b);
    if(o == 0)
        return distance(bottom, a) <= distance(bottom, b);
    return o == 1;
}

/// 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, m_ind = 0;
    float x, y;
    vector<Point> p;
    fin>>n>>x>>y;
    
    p.reserve(n * sizeof(Point));
    bottom = *(new Point(x, y));
    p.push_back(bottom);  
    
    /// find the bottom-most point
    for(i = 1; i < n; i++) {
        fin>>x>>y;
        p.push_back(*(new Point(x, y)));
        if(y < bottom.y || (y == bottom.y && x <= bottom.x)) {
            bottom = *(new Point(x, y));
            m_ind = i;
        }
    }
    
    /// push the bottom-most point into the solution
    swap(p[m_ind], p[0]);

    /// sort the rest of n - 1 points accordingly
    sort(p.begin() + 1, p.end(), comparer);

    int m = 1;
    /// eliminate the irrelevant points: if we have more points with the same polar angle
    /// only keep the one the farthest from bottom-most point
    for(i = 1; i < n; i++) {
        while(i < n - 1 && orientation_Test(bottom, p[i], p[i+1]) == 0)
            i++;
        p[m] = p[i];
        m++;
    }

    if(m < 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]);
    s.push(p[2]);

    /// process the remaining points
    for(i = 3; i < m; i++) {    
        /// eliminate points untill the first 2 points in the stack make
        /// a left turn (counterclockwise turn)
        while(orientation_Test(secondInStack(s), s.top(), p[i]) != 1)
            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;
}