Cod sursa(job #3255538)

Utilizator vlad7654vladimir manescu vlad7654 Data 10 noiembrie 2024 22:44:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;
int n,head;
struct Point{
    double x,y;
    friend bool operator<(Point A,Point B){
        if(A.x<B.x){
            return 1;
        }
        if(A.x==B.x and A.y<B.y){
            return 1;
        }
        return 0;
    }
};
Point points[NMAX],st[NMAX];
double cross_product(Point O,Point A,Point B){
    return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
bool cmp(Point A,Point B){
    return cross_product(points[1],A,B)<0;
}
void sort_points(){
    int pos=1;
    for(int i=2; i<=n; i++){
        if(points[i]<points[pos]){
            pos=i;
        }
    }
    swap(points[1],points[pos]);
    sort(points+2,points+n+1,cmp);
}
void convex_hull(){
    sort_points();
    st[1]=points[1];
    st[2]=points[2];
    head=2;
    for(int i=3;i<=n;i++){
        while(head>=2 and cross_product(st[head-1],st[head],points[i])>0){
            head--;
        }
        st[++head]=points[i];
    }
}

int main(){
    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>points[i].x>>points[i].y;
    }
    convex_hull();
    fout<<head<<'\n';
    for(int i=head; i>=1; i--){
        fout<<setprecision(6)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
    }
}