Cod sursa(job #3206942)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 24 februarie 2024 15:07:38
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 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;

pair < long double, long double > points[NMAX];
int hull[NMAX];
int H;

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

long double get_angle(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);
}

bool is_counter_clockwise(pair < long double, long double > a,
                                 pair < long double, long double > b,
                                 pair < long double, long double > c){
    return get_angle(a, b, c) < 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[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].second < downmost_y){
            downmost_y = points[i].second;
            downmost_i = i;
        }else if(points[i].second == downmost_y &&
                 points[i].first < points[downmost_i].first){
                    downmost_y = points[i].second;
                    downmost_i = i;
        }
    }

    auto downmost_pt = points[downmost_i];
    sort(points, points + N, [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);
         });
	
	
    return 0;
	// solutia da 0, dar ma intereseaza doar daca atan2 este optimizat
    // graham();
    fout << H << "\n";
    for(int i = 0; i < H; i++){
        int idx = hull[i];
        fout << fixed << setprecision(12) << points[idx].first << " ";
        fout << fixed << setprecision(12) << points[idx].second << " ";
        fout << "\n";
    }
    return 0;
}