Pagini recente » Cod sursa (job #166349) | Cod sursa (job #2963207) | Cod sursa (job #2961815) | Cod sursa (job #2833361) | Cod sursa (job #3206793)
#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;
pair < long double, long double > points[NMAX];
int hull[NMAX];
int H;
void read(){
fin >> N;
for(int i = 0; i < N; i++){
fin >> points[i].first >> points[i].second;
}
}
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[0] = 0;
hull[1] = 1;
H = 2;
for(int i = 2; i < N; i++){
while(H >= 2 &&
!is_counter_clockwise(points[hull[H - 2]],
points[hull[H - 1]],
points[i])){
H--;
}
hull[H++] = i;
}
}
int main()
{
read();
/// SOLVE 2 - Graham Scan (points.size() * log(points.size()))
int downmost_i = 0;
int downmost_y = 1000000001;
for(int i = 0; i < N; 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, points + N, [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 << H << "\n";
for(int i = 0; i < H; i++){
int idx = hull[i];
fout << fixed << setprecision(12) << points[idx].first << " ";
fout << fixed << setprecision(12) << points[idx].second << " ";
fout << "\n";
}
return 0;
}