Pagini recente » Cod sursa (job #2311480) | Istoria paginii runda/oni_11_12_6/clasament | preoji/clasament/9 | Cod sursa (job #1433087) | Cod sursa (job #2495730)
#include <fstream>
#include <stack>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
double x, y;
Point(double a = 0, double b = 0): x(a), y(b) {}
};
vector<Point> p;
/// test whether a turn is left or not
int isLeft(const Point &P,const Point &Q,const Point &R){
return ((Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x)>0);
}
/// order points by y
bool comparer(const Point& a, const Point& b) {
return isLeft(p[0], a, b);
}
/// find the 2nd point in stack
Point secondInStack(stack<Point> &s) {
Point p = s.top();
s.pop();
Point sec = s.top();
s.push(p);
return sec;
}
int main() {
int n, i;
float x, y;
p.reserve(n * sizeof(Point));
fin>>n;
for(i = 0; i < n; i++) {
fin>>x>>y;
p.push_back(*(new Point(x, y)));
if(p[0].x > p[i].x || (p[0].x == p[i].x && p[0].y > p[i].y))
swap(p[0], p[i]);
}
/// sort the points
sort(p.begin() + 1, p.end(), comparer);
if(n < 3) {
fout<<"Convex hull can not be determined";
return 0;
}
/// push the first 3 points into a stack
stack<Point> s;
s.push(p[0]);
s.push(p[1]);
/// process the remaining points
for(i = 2; i < n; i++) {
/// eliminate points until the first 2 points in the stack make
/// a left turn (counterclockwise turn)
while(!isLeft(secondInStack(s), s.top(), p[i]) && s.size() >= 2)
s.pop();
s.push(p[i]);
}
int k = s.size();
fout<<s.size()<<endl;
/// print points in trigonometrical order - reverse the stack
vector<Point> convex_hull;
while(!s.empty()) {
convex_hull.push_back(s.top());
s.pop();
}
for(i = k - 1; i >= 0; i--)
fout<<fixed<<setprecision(6)<<convex_hull[i].x<<" "<<convex_hull[i].y<<endl;
return 0;
}