Cod sursa(job #3206743)

Utilizator manudragoDragomir Manuel manudrago Data 23 februarie 2024 22:15:42
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <stack>

using namespace std;

const int NMAX = 120005;

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

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

void read(){
    fin >> N;
    for(int i = 0; i < N; i++){
        long 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];
    long double xa = a.first;
    long double ya = a.second;
    long double xb = b.first;
    long double yb = b.second;
    long double xc = c.first;
    long double yc = c.second;
    long 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();
}

void graham(){
    hull.push_back(0);
    hull.push_back(1);

    for(int i = 2; i < points.size(); i++){
        auto p1 = hull[hull.size() - 2];
        auto p2 = hull[hull.size() - 1];

        while(hull.size() > 2 && !is_counter_clockwise(p1, p2, i)){
            hull.pop_back();
            p1 = hull[hull.size() - 2];
            p2 = hull[hull.size() - 1];
        }

        hull.push_back(i);
    }

}

int main()
{
    read();

    /**
    /// SOLVE 1 - Jarvis march O(points.size() * hull.size())
    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 << fixed << setprecision(12) << points[idx].first << " ";
        fout << fixed << setprecision(12) << points[idx].second << " ";
        fout << "\n";
    }*/

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

    auto downmost_pt = points[downmost_i];
    sort(points.begin(), points.end(), [=](auto a, auto b){
            return atan2(a.second - downmost_pt.second, a.first - downmost_pt.first)
                < atan2(b.second - downmost_pt.second, b.first - downmost_pt.first);
         });

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