Pagini recente » Cod sursa (job #2272200) | Cod sursa (job #2434789) | Cod sursa (job #2701335) | Cod sursa (job #1441602) | Cod sursa (job #2699651)
#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
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;
}