Cod sursa(job #3196415)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 23 ianuarie 2024 20:15:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in  ("infasuratoare.in");
ofstream out("infasuratoare.out");

#define maxN 120000
struct point{
    double x,y;
}v[maxN+1];

#define maxVal 1000000000
double minx=maxVal,miny=maxVal;
vector <point>st;

bool cmp(point a,point b){
    return (-minx+a.x)*(-miny+b.y)>(-miny+a.y)*(-minx+b.x);
}

double slope(point a,point b){
    return a.x*b.y-a.y*b.x;
}

int orient(point a,point b,point c){
    double val=slope(a,b)+slope(b,c)+slope(c,a);
    if(val>0){
        return 1;
    }
    else{
        if(val==0){
            return 2;
        }
        else{
            return 3;
        }
    }
}

int main(){
    double x,y;
    int n;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>v[i].x>>v[i].y;
        if(v[i].y<miny){
            miny=v[i].y;
            minx=v[i].x;
            swap(v[1],v[i]);
        }
    }
    sort(v+2,v+n+1,cmp);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i=3;i<=n;i++){
        while(st.size()>1 && orient(st[st.size()-2],st[st.size()-1],v[i])!=1){
            st.pop_back();
        }
        st.push_back(v[i]);
    }
    out<<st.size()<<'\n';
    for(int i=0;i<st.size();i++){
        out<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
    }

}