Cod sursa(job #3206961)

Utilizator manudragoDragomir Manuel manudrago Data 24 februarie 2024 15:47:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 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;
    long double angle;
};

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

bool is_counter_clockwise(Point a, Point b, Point c){
    return ((b.y - a.y) * (c.x - b.x) -
           (b.x - a.x) * (c.y - b.y)) < 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()))
    for(int i = 1; i < N; i++){
        if(points[i].y < points[0].y){
            swap(points[i], points[0]);
        }
    }

    points[0].angle = 0;

    for(int i = 1; i <= N; i++){
        points[i].angle = atan2(points[i].y - points[0].y,
                                points[i].x - points[0].x);
    }

    sort(points + 1, points + N, [](Point a, Point b){
            return a.angle < b.angle;
         });

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