Pagini recente » Cod sursa (job #1998300) | Cod sursa (job #1523320) | Cod sursa (job #1921288) | Cod sursa (job #1612047) | Cod sursa (job #3247268)
#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;
}