Pagini recente » Istoria paginii runda/oni_2006_10_z1 | Istoria paginii runda/preoji_6/clasament | Cod sursa (job #2692129) | Cod sursa (job #1573024) | Cod sursa (job #2495682)
#include <fstream>
#include <stack>
#include <vector>
#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) {}
} bottom;
double orientation_Test(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
/// colinear points
if(val == 0)
return 0;
/// clockwise
else if(val > 0)
return -1;
/// counterclockwise
return 1;
}
double distance(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
/// sort counteclockwise to bottom and by distance if equal angle
bool comparer(const Point& a, const Point& b) {
int o = orientation_Test(bottom, a, b);
if(o == 0)
return distance(bottom, a) <= distance(bottom, b);
return o == 1;
}
/// 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, m_ind = 0;
float x, y;
vector<Point> p;
fin>>n>>x>>y;
p.reserve(n * sizeof(Point));
bottom = *(new Point(x, y));
p.push_back(bottom);
/// find the bottom-most point
for(i = 1; i < n; i++) {
fin>>x>>y;
p.push_back(*(new Point(x, y)));
if(y < bottom.y || (y == bottom.y && x <= bottom.x)) {
bottom = *(new Point(x, y));
m_ind = i;
}
}
/// push the bottom-most point into the solution
swap(p[m_ind], p[0]);
/// sort the rest of n - 1 points accordingly
sort(p.begin() + 1, p.end(), comparer);
int m = 1;
/// eliminate the irrelevant points: if we have more points with the same polar angle
/// only keep the one the farthest from bottom-most point
for(i = 1; i < n; i++) {
while(i < n - 1 && orientation_Test(bottom, p[i], p[i+1]) == 0)
i++;
p[m] = p[i];
m++;
}
if(m < 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]);
s.push(p[2]);
/// process the remaining points
for(i = 3; i < m; i++) {
/// eliminate points untill the first 2 points in the stack make
/// a left turn (counterclockwise turn)
while(orientation_Test(secondInStack(s), s.top(), p[i]) != 1)
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;
}