Pagini recente » Cod sursa (job #2451181) | Cod sursa (job #259034) | Cod sursa (job #990278) | Cod sursa (job #1487819) | Cod sursa (job #3247224)
#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(), [¢roid](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;
}