Cod sursa(job #3213174)

Utilizator AlexRzvAlex Razvan AlexRzv Data 12 martie 2024 16:59:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 120000;

ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.out");

struct punct{
    long double x,y;
    long double angle;
};

int n;
punct points[NMAX + 1];
int H[NMAX + 1];
int nr;

void read(){
    fin >> n;
    for(int i = 1;i<=n;++i)
        fin >> points[i].x >> points[i].y;
}

bool clockwise(punct a, punct b, punct c){
    return ((b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)) < 0;
}

void graham(){
    H[1] = 1;
    H[2] = 2;
    nr = 2;
    for(int i = 2;i<=n;++i){
        while(nr >= 2 && !clockwise(points[H[nr - 1]], points[H[nr]], points[i]))
            nr--;
        H[++nr] = i;
    }
}

int main(){

    read();
    for(int i = 2;i<=n;++i)
        if(points[i].y < points[1].y)
            swap(points[i],points[1]);
    points[1].angle = 0;
    for(int i = 2;i<=n;++i)
        points[i].angle = atan2(points[i].y - points[1].y, points[i].x - points[1].x);
    sort(points + 1, points + n + 1, [](punct p1, punct p2){return p1.angle < p2.angle;});
    graham();
    fout << nr << '\n';
    for(int i = 1;i<=nr;++i){
        int poz = H[i];
        fout << fixed << setprecision(12) << points[poz].x << ' ';
        fout << fixed << setprecision(12) << points[poz].y <<  ' ';
        fout << '\n';
    }
    return 0;
}