Cod sursa(job #3206799)

Utilizator manudragoDragomir Manuel manudrago Data 24 februarie 2024 09:56:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

const int NMAX = 120005;

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

int N;

struct Point{
    long double x, y;
};

Point points[NMAX];
int hull[NMAX];
int H;

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

long double get_angle(Point a, Point b, Point c){
    return (b.y - a.y) * (c.x - b.x) -
           (b.x - a.x) * (c.y - b.y);
}

bool is_counter_clockwise(Point a, Point b, Point c){
    return get_angle(a, b, c) < 0;
}

void graham(){
    hull[0] = 0;
    hull[1] = 1;
    H = 2;

    for(int i = 2; i < N; i++){
        while(H >= 2 &&
              !is_counter_clockwise(points[hull[H - 2]],
                                    points[hull[H - 1]],
                                    points[i])){
            H--;
        }
        hull[H++] = i;
    }

}

int main()
{
    read();

    /// SOLVE 2 - Graham Scan (points.size() * log(points.size()))
    int downmost_i = 0;
    int downmost_y = 1000000001;
    for(int i = 0; i < N; i++){
        if(points[i].y < downmost_y){
            downmost_y = points[i].y;
            downmost_i = i;
        }else if(points[i].y == downmost_y &&
                 points[i].x < points[downmost_i].x){
                    downmost_y = points[i].y;
                    downmost_i = i;
        }
    }

    auto downmost_pt = points[downmost_i];
    sort(points, points + N, [downmost_pt](auto a, auto b){
            if(get_angle(downmost_pt, a, b) <= 0){
                return true;
            }
            return false;
         });

    graham();
    fout << H << "\n";
    for(int i = 0; i < H; i++){
        int idx = hull[i];
        fout << fixed << setprecision(12) << points[idx].x << " ";
        fout << fixed << setprecision(12) << points[idx].y << " ";
        fout << "\n";
    }
    return 0;
}