Cod sursa(job #2699649)

Utilizator Silviu45Dinca Silviu Silviu45 Data 25 ianuarie 2021 13:13:18
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("../infasuratoare.in");
ofstream fout("infasuratoare.out");



void read(int &n,pair<float,float> points[]){
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> points[i].first >> points[i].second;
}

//return 0 - if a,b,c are coliniar
//return 1 - if a b c orientation clockwise
//return -1 - if a b c orientation is non-clockwise
int orientation(pair<float,float> a,pair<float,float> b,pair<float,float> c){
    //Varianta 1 . Proasta , pentru ca ma bazez pe compilatorul care are o limita de calcul al zecimalelor
//    //calculate the slobe of ab segment
//    float slope_ab = (b.second - a.second)/(b.first - a.first);
//    //calculate the slope of bc segment
//    float slope_bc = (c.second-b.second)/(c.first-b.first);
//    float val = slope_ab - slope_bc;
    float val = (b.second-a.second)*(c.first-b.first) - (c.second-b.second)*(b.first-a.first);
    if(val == 0)//coliniare
        return 0;
    else if(val > 0)//slope_ab - slope_bc > 0 , see sketch
        return 1;
    else return -1;
}

void convexHullv2(int n,pair<float,float> points[]){
    int first_pointIndex = 1;
    vector <int> result;
    //get the point most on the left
    for(int i = 1; i <= n; i++)
        if(points[i].first < points[first_pointIndex].first)
            first_pointIndex = i;
    //start
    int current_pointIndex = first_pointIndex,next_index;
    do{
        result.push_back(current_pointIndex);

        next_index = (current_pointIndex+1)%n;
        if(next_index == 0) next_index = n;

        //get the point which forms maximum left angle with current point
        for(int i = 1; i <= n; i++){
            if(orientation(points[current_pointIndex],points[i],points[next_index]) == -1)//if there are counterclockwise
                next_index = i;
        }
        //fout << "p : " << points[current_pointIndex].first << " " << points[current_pointIndex].second <<
        //     " next : " << points[next_index].first << " " << points[next_index].second << "\n";

        current_pointIndex = next_index;//the next point will be the most counterclockwise point

    }while(current_pointIndex != first_pointIndex);

    reverse(result.begin(),result.end());

    for(auto r : result)
       fout <<  points[r].first << " " << points[r].second << endl;
}

int main()
{
    int n;
    pair<float,float> points[1205];
    if(fin.is_open())
    {
        read(n, points);
        convexHullv2(n,points);
    }
    return 0;
}