Cod sursa(job #3247224)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 6 octombrie 2024 13:35:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define MODULE_MIN_COORD_VALUE 1000000000
///https://infoarena.ro/problema/infasuratoare

using namespace std;

struct Coordinates {
    double x;
    double y;
};

double cross(const Coordinates& O, const Coordinates& A, const Coordinates& B){
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

void swap(Coordinates& a, Coordinates& b){
    Coordinates temp = a;
    a = b;
    b = temp;
}

Coordinates calculateCentroid(const vector<Coordinates>& hull){
    double sumX = 0, sumY = 0;
    for (const auto& p : hull){
        sumX += p.x;
        sumY += p.y;
    }
    Coordinates centroid;
    centroid.x = sumX / hull.size();
    centroid.y = sumY / hull.size();
    return centroid;
}

double calculateAngle(const Coordinates& center, const Coordinates& point){
    return atan2(point.y - center.y, point.x - center.x);
}

void sortPointsByAngle(vector<Coordinates>& hull){
    Coordinates centroid = calculateCentroid(hull);
    sort(hull.begin(), hull.end(), [&centroid](const Coordinates& a, const Coordinates& b) {
        double angleA = calculateAngle(centroid, a);
        double angleB = calculateAngle(centroid, b);
        return angleA < angleB;
    });
}

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

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

vector<Coordinates> readCoordinatesFromFile(const string& filename){
    vector<Coordinates> coordinates;
    ifstream inputFile(filename);
    int n;
    inputFile >> n ;
    Coordinates coord;
    for (int i = 0 ; i < n ; i++){
        if (inputFile >> coord.x >> coord.y){
            coord.x+=MODULE_MIN_COORD_VALUE;
            coord.y+=MODULE_MIN_COORD_VALUE;
            coordinates.push_back(coord);
        }
    }
    inputFile.close();
    return coordinates;
}

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

vector<Coordinates> convexHull(vector<Coordinates>& points){
    vector<Coordinates> hull;
    for (const auto& p : points){
        while (hull.size() >=2 && cross(hull[hull.size()-2], hull[hull.size()-1], p) <=0){
            hull.pop_back();
        }
        hull.push_back(p);
    }
    size_t lowerHullSize = hull.size();
    for (int i = points.size()-2 ; i>=0 ; --i){
        while (hull.size() > lowerHullSize && cross (hull[hull.size()-2], hull[hull.size()-1], points [i]) <=0){
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    if (!hull.empty()) {
        hull.pop_back();
    }
    return hull;
}

int main()
{   string inputFilename = "infasuratoare.in";
    string outputFilename = "infasuratoare.out";
    vector<Coordinates> coordinates = readCoordinatesFromFile(inputFilename);
    quicksort(coordinates, 0, coordinates.size() - 1);
    vector<Coordinates> hull = convexHull(coordinates);
    sortPointsByAngle(hull);
    writeCoordinatesToFile(hull, outputFilename);
    return 0;
}