Pagini recente » Cod sursa (job #1728116) | Cod sursa (job #1388190) | Cod sursa (job #2170742) | Cod sursa (job #2938535) | Cod sursa (job #2921713)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <iomanip>
#define epsilon 1e-12
using namespace std;
typedef pair<double,double> Point;
Point points[150000];
Point operator-(Point a, Point b){
return Point(a.first - b.first, a.second - b.second);
}
double angle(Point a){
return atan2(a.first, a.second);
}
bool concave(Point a, Point b, Point c){
double theta1 = angle(a - b);
double theta2 = angle(c - b);
double diff = theta2 - theta1;
if(diff > M_PI + epsilon)
return false;
else if(diff < -M_PI - epsilon)
return true;
else if(diff > epsilon)
return true;
else
return false;
}
struct {
bool operator()(Point a, Point b) const { return angle(a - points[0]) < angle(b - points[0]); }
} angularLess;
int main(){
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x, y;
fin >> n;
for(int i = 0; i < n; ++i){
fin >> points[i].first >> points[i].second;
}
// find leftmost point
for(int i = 1; i < n; ++i){
if(points[i].first < points[0].first)
swap(points[0], points[i]);
}
// angular sort
sort(points + 1, points + n, angularLess);
stack<Point> stk;
stk.push(points[0]);
stk.push(points[1]);
// construct hull
for(int i = 2; i < n; ++i){
while(true){
Point last = stk.top();
stk.pop();
Point second_last = stk.top();
if(!concave(second_last, last, points[i])){
stk.push(last);
stk.push(points[i]);
break;
}
}
}
fout << stk.size() << "\n";
while(!stk.empty()){
fout << fixed << setprecision(6) << stk.top().first << " " << stk.top().second << "\n";
stk.pop();
}
}