Pagini recente » Cod sursa (job #1229881) | Cod sursa (job #1530469) | Cod sursa (job #2170261) | Cod sursa (job #420974) | Cod sursa (job #3206721)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
const int NMAX = 120005;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
vector < pair < double, double > > points;
vector < int > hull;
void read(){
fin >> N;
for(int i = 0; i < N; i++){
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];
double xa = a.first;
double ya = a.second;
double xb = b.first;
double yb = b.second;
double xc = c.first;
double yc = c.second;
double slopes_diff = (yb - ya) * (xc - xb) - (xb - xa) * (yc - yb);
if(slopes_diff < 0){
return true;
}
return false;
}
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(last_point, next_candidate, i)){
next_candidate = i;
}
}
}
hull.push_back(next_candidate);
}
hull.pop_back();
}
int main()
{
read();
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);
fout << hull.size() << "\n";
for(int i = hull.size() - 1; i >=0; i--){
int idx = hull[i];
fout << points[idx].first << " " << points[idx].second << "\n";
}
return 0;
}