Cod sursa(job #3206757)

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

using namespace std;

const int NMAX = 120005;

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

int N;
vector < pair < long double, long double > > points;
deque < 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;
//}

bool is_counter_clockwise(pair < long double, long double > a,
                           pair < long double, long double > b,
                           pair < long double, long double > c){
    return ((b.second - a.second) * (c.first - b.first) -
           (b.first - a.first) * (c.second - b.second)) < 0;
}

//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(points[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++){
        while(hull.size() >= 2 &&
              !is_counter_clockwise(points[hull[hull.size() - 2]],
                                    points[hull[hull.size() - 1]],
                                    points[i])){
            hull.pop_back();
        }

        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(), [downmost_pt](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;
}