Pagini recente » Cod sursa (job #444426) | Cod sursa (job #2840898) | Cod sursa (job #512548) | Cod sursa (job #877495) | Cod sursa (job #3206765)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <stack>
#include <deque>
using namespace std;
const int NMAX = 120005;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
vector < pair < long double, long double > > points;
deque < int > hull;
void read(){
fin >> N;
for(int i = 0; i < N; i++){
long double x, y;
fin >> x >> y;
points.push_back({x, y});
}
}
//bool is_counter_clockwise(int ia, int ib, int ic){
// auto a = points[ia];
// auto b = points[ib];
// auto c = points[ic];
// long double xa = a.first;
// long double ya = a.second;
// long double xb = b.first;
// long double yb = b.second;
// long double xc = c.first;
// long double yc = c.second;
// long double slopes_diff = (yb - ya) * (xc - xb) - (xb - xa) * (yc - yb);
// if(slopes_diff < 0){
// return true;
// }
// return false;
//}
long double get_angle(pair < long double, long double > a,
pair < long double, long double > b,
pair < long double, long double > c){
return (b.second - a.second) * (c.first - b.first) -
(b.first - a.first) * (c.second - b.second);
}
bool is_counter_clockwise(pair < long double, long double > a,
pair < long double, long double > b,
pair < long double, long double > c){
return get_angle(a, b, c) < 0;
}
//void jarvis(int start_idx){
// hull.push_back(start_idx);
// while(hull.size() == 1 || hull.back() != hull.front()){
// int last_point = hull.back();
// int next_candidate = (last_point + 1) % points.size();
// for(int i = 0; i < points.size(); i++){
// if(i != next_candidate){
// if(is_counter_clockwise(points[last_point, next_candidate, i)){
// next_candidate = i;
// }
// }
// }
// hull.push_back(next_candidate);
// }
// hull.pop_back();
//}
void graham(){
hull.push_back(0);
hull.push_back(1);
for(int i = 2; i < points.size(); i++){
while(hull.size() >= 2 &&
!is_counter_clockwise(points[hull[hull.size() - 2]],
points[hull[hull.size() - 1]],
points[i])){
hull.pop_back();
}
hull.push_back(i);
}
}
int main()
{
read();
/**
/// SOLVE 1 - Jarvis march O(points.size() * hull.size())
int leftmost_idx = 0;
int leftmost_x = 1000000001;
for(int i = 0; i < points.size(); i++){
if(points[i].first < leftmost_x){
leftmost_x = points[i].first;
leftmost_idx = i;
}
}
jarvis(leftmost_idx);
sort(hull.begin(), hull.end(), [](int ia, int ib){
auto a = points[ia];
auto b = points[ib];
return atan2(a.second, a.first) < atan2(b.second, b.first);
});
fout << hull.size() << "\n";
for(auto idx: hull){
fout << fixed << setprecision(12) << points[idx].first << " ";
fout << fixed << setprecision(12) << points[idx].second << " ";
fout << "\n";
}*/
/// SOLVE 2 - Graham Scan (points.size() * log(points.size()))
int downmost_i = 0;
int downmost_y = 1000000001;
for(int i = 0; i < points.size(); i++){
if(points[i].second < downmost_y){
downmost_y = points[i].second;
downmost_i = i;
}else if(points[i].second == downmost_y &&
points[i].first > points[downmost_i].first){
downmost_y = points[i].second;
downmost_i = i;
}
}
auto downmost_pt = points[downmost_i];
sort(points.begin(), points.end(), [downmost_pt](auto a, auto b){
return atan2(a.second - downmost_pt.second, a.first - downmost_pt.first)
< atan2(b.second - downmost_pt.second, b.first - downmost_pt.first);
});
graham();
fout << hull.size() << "\n";
for(auto idx: hull){
fout << fixed << setprecision(12) << points[idx].first << " ";
fout << fixed << setprecision(12) << points[idx].second << " ";
fout << "\n";
}
return 0;
}