Cod sursa(job #2836889)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 21 ianuarie 2022 08:57:31
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;

int N;
struct point{
    double x, y;
};
point points[NMAX], p0;

int orientation(point p, point q, point r){
    double val=(q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
    if(val==0) return 0; ///collinear
    if(val>0) return 1; ///clockwise
    return 2; ///counterclockwise
}

double dist(point p, point q){
    return (q.x-p.x)*(q.x-p.x)+(q.y-p.y)*(q.y-p.y);
}

bool comp(point A, point B){
    int o=orientation(p0,A,B);
    if(o==0)
        return dist(p0,A)<dist(p0,B);
    if(o==1) return 0;
    return 1;
}

point nexToTop(stack<point> st){
    point p=st.top();
    st.pop();
    point res=st.top();
    st.push(p);
    return res;
}

void afisare(stack<point> st){
    if(!st.empty()){
        point res=st.top();
        st.pop();
        afisare(st);
        fout<<res.x<<' '<<res.y<<'\n';
    }
}

void convexHull()
{
    int mn=1;
    for(int i=2;i<=N;i++){
        if(points[i].y<points[mn].y)
            mn=i;
        else if(points[i].y==points[mn].y and points[i].x<points[mn].x)
            mn=i;
    }
    p0=points[mn];

    swap(points[1],points[mn]);
    sort(points+2,points+N+1,comp);

    stack<point> st;
    st.push({points[1]});
    st.push({points[2]});
    st.push({points[3]});
    for(int i=4;i<=N;i++){
        while(st.size()>=3 and orientation(nexToTop(st),st.top(),points[i])!=2)
            st.pop();
        st.push(points[i]);
    }

    fout<<st.size()<<'\n';
    fout<<fixed<<setprecision(12);
    afisare(st);
}

int main()
{
    fin>>N;
    double x, y;
    for(int i=1;i<=N;i++){
        fin>>x>>y;
        points[i]={x,y};
    }

    convexHull();

    fin.close();
    fout.close();
    return 0;

}