Cod sursa(job #3247268)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 6 octombrie 2024 17:29:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <iomanip>

#define MOD_MIN_VALUE 1000000000

using namespace std;

struct points{
    double x;
    double y;
};

double cross(const points& O, const points& A, const points &B){
    ///relative position of B to OA
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<points> convex_hull(vector<points>& coordinates){
    ///building the convex hull
    vector<points> hull;
    size_t n = coordinates.size();
    for (size_t i=0 ; i < n ; i++){
        while(hull.size() >=2 && cross(hull[hull.size()-2], hull[hull.size()-1], coordinates[i]) <= 0){
            hull.pop_back();
        }
        hull.push_back(coordinates[i]);
    }
    size_t lowerHullSize = hull.size();
    for (int i = coordinates.size()-2 ; i>=0 ; i--){
        while (hull.size() > lowerHullSize && cross(hull[hull.size()-2], hull[hull.size()-1], coordinates[i]) <= 0){
            hull.pop_back();
        }
        hull.push_back(coordinates[i]);
    }
    if (!hull.empty()){
        hull.pop_back(); /// removing the point which was added twice
    }
    return hull;

}

int partition(vector<points>& coordinates, int low, int high){
    points pivot = coordinates[high];
    int i = low - 1;
    for ( int j = low ; j < high ; j++ ){
        if (coordinates[j].x < pivot.x || (coordinates[j].x == pivot.x && coordinates[j].y < pivot.y)){
            i++;
            swap(coordinates[i], coordinates[j]);
        }
    }
    swap(coordinates[i+1], coordinates[high]);
    return i+1;
}

void quicksort(vector<points>& coordinates, int low, int high){
    if (low<high){
        int pi = partition(coordinates, low, high);
        quicksort(coordinates, low, pi-1);
        quicksort(coordinates, pi+1, high);
    }
}

vector <points> readCoordinatesFromFile(const string& filename){
    ifstream inputFile(filename);
    vector <points> arr;
    int n;
    inputFile >> n;
    arr.resize(n);
    for (int i = 0; i < n ; i++){
        inputFile >> arr[i].x >> arr[i].y;
        arr[i].x+=MOD_MIN_VALUE;
        arr[i].y+=MOD_MIN_VALUE;
    }
    inputFile.close();
    return arr;
}

void writeCoordinatesToFile(const vector<points> arr, const string& filename){
    ofstream outputFile(filename);
    outputFile << arr.size() << endl;
    outputFile << fixed << setprecision(6);
    for (size_t i = 1 ; i < arr.size(); i++){
        outputFile << arr[i].x - MOD_MIN_VALUE<< " "
                   << arr[i].y - MOD_MIN_VALUE<< " " << endl;
    }
    outputFile << arr[0].x - MOD_MIN_VALUE<< " "
               << arr[0].y - MOD_MIN_VALUE<< " " << endl;
    outputFile.close();
}

int main()
{
    string inputFile = "infasuratoare.in";
    string outputFile = "infasuratoare.out";
    vector<points> coordinates = readCoordinatesFromFile(inputFile);
    quicksort(coordinates, 0, coordinates.size() - 1);
    vector<points> hull = convex_hull(coordinates);
    writeCoordinatesToFile(hull, outputFile);
    return 0;
}