Cod sursa(job #3206722)

Utilizator manudragoDragomir Manuel manudrago Data 23 februarie 2024 21:43:26
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

const int NMAX = 120005;

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

int N;
vector < pair < double, double > > points;
vector < int > hull;

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

bool is_counter_clockwise(int ia, int ib, int ic){
    auto a = points[ia];
    auto b = points[ib];
    auto c = points[ic];
    double xa = a.first;
    double ya = a.second;
    double xb = b.first;
    double yb = b.second;
    double xc = c.first;
    double yc = c.second;
    double slopes_diff = (yb - ya) * (xc - xb) - (xb - xa) * (yc - yb);
    if(slopes_diff < 0){
        return true;
    }
    return false;
}

void jarvis(int start_idx){
    hull.push_back(start_idx);
    while(hull.size() == 1 || hull.back() != hull.front()){
        int last_point = hull.back();
        int next_candidate = (last_point + 1) % points.size();
        for(int i = 0; i < points.size(); i++){
            if(i != next_candidate){
                if(is_counter_clockwise(last_point, next_candidate, i)){
                    next_candidate = i;
                }
            }
        }
        hull.push_back(next_candidate);
    }
    hull.pop_back();
}

int main()
{
    read();

    int leftmost_idx = 0;
    int leftmost_x = 1000000001;
    for(int i = 0; i < points.size(); i++){
        if(points[i].first < leftmost_x){
            leftmost_x = points[i].first;
            leftmost_idx = i;
        }
    }

    jarvis(leftmost_idx);
    sort(hull.begin(), hull.end(), [](int ia, int ib){
            auto a = points[ia];
            auto b = points[ib];
            return atan2(a.second, a.first) < atan2(b.second, b.first);
         });

    fout << hull.size() << "\n";
    for(auto idx: hull){
        fout << points[idx].first << " " << points[idx].second << "\n";
    }
    return 0;
}