Pagini recente » Cod sursa (job #2178176) | Cod sursa (job #3038636) | Cod sursa (job #2191114) | Cod sursa (job #404868) | Cod sursa (job #2921719)
#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 points2[150000];
int indx[150000];
double angles[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()(int a, int b) const { return angles[a] < angles[b]; }
} 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]);
}
for(int i = 1; i < n; ++i){
indx[i] = i;
angles[i] = angle(points[i] - points[0]);
}
sort(indx + 1, indx + n, angularLess);
for(int i = 0; i < n; ++i)
points2[i] = points[indx[i]];
stack<Point> stk;
stk.push(points2[0]);
stk.push(points2[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, points2[i])){
stk.push(last);
stk.push(points2[i]);
break;
}
}
}
fout << stk.size() << "\n";
while(!stk.empty()){
fout << fixed << setprecision(6) << stk.top().first << " " << stk.top().second << "\n";
stk.pop();
}
}