Cod sursa(job #2836893)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 21 ianuarie 2022 09:06:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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, st[NMAX];

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;
}

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);

    int vf=0;
    st[++vf]=points[1];
    st[++vf]=points[2];
    for(int i=3;i<=N;i++){
        while(vf>1 and orientation(st[vf-1],st[vf],points[i])!=2)
            vf--;
        st[++vf]=points[i];
    }

    fout<<vf<<'\n';
    fout<<fixed<<setprecision(12);
    for(int i=1;i<=vf;i++)
        fout<<st[i].x<<' '<<st[i].y<<'\n';
}

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;

}