Cod sursa(job #2496150)

Utilizator turtoieduardEduard Turtoi turtoieduard Data 20 noiembrie 2019 11:59:24
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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 st[120005];

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 cmp(const Point &P, const Point &Q) {
    return isLeft(p[1], 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;
    fin>>n;
    p.resize(n+1);

    for(int i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;
 
    for(int i=2;i<=n;i++)
        if(p[1].x>p[i].x || (p[1].x==p[i].x && p[1].y>p[i].y))
                swap(p[1],p[i]);
 
    sort(p.begin() + 2, p.end(), cmp);
    /*st[1]=1; st[2]=2;
    tp=2;
    for(int i=3;i<=n;i++){
        while(tp>=2 && !isLeft(p[st[tp-1]],p[st[tp]],p[i])) --tp;
        st[++tp]=i;
 
    }
 
    fout<<tp<<'\n';
    for(int i=1;i<=tp;i++)
        fout<<fixed<<setprecision(6)<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
    */
    s.push(p[1]);
    s.push(p[2]);
    for(int i = 3; 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';


}