Pagini recente » Cod sursa (job #1782380) | Arhiva de probleme | Cod sursa (job #1376618) | Cod sursa (job #2794979) | Cod sursa (job #1178433)
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#define x first
#define y second
using namespace std;
typedef pair<double, double> Point;
const double EPS = 1e-9;
class ConvexHull {
public:
ConvexHull(const vector<Point> &points):
hull(set< pair<double, Point> >()),
center(Point(0.0, 0.0)) {
for (int i = 0; i < 3; ++i) {
center.x += points[i].x;
center.y += points[i].y;
}
center.x /= 3.0;
center.y /= 3.0;
for (int i = 0; i < 3; ++i)
hull.insert(make_pair(Alpha(points[i]), points[i]));
for (int i = 3; i < int(points.size()); ++i)
Insert(points[i]);
}
void Insert(const Point &point) {
double alpha = Alpha(point);
set< pair<double, Point> >::iterator p = hull.lower_bound(make_pair(alpha, point));
if (Det(Previous(p)->second, point, p->second) < EPS)
return;
while (int(hull.size()) > 1 && Det(point, p->second, Next(p)->second) < EPS) {
hull.erase(p);
p = hull.lower_bound(make_pair(alpha, point));
}
p = Previous(p);
while (int(hull.size()) > 1 && Det(Previous(p)->second, p->second, point) < EPS) {
hull.erase(p);
p = Previous(hull.lower_bound(make_pair(alpha, point)));
}
hull.insert(make_pair(alpha, point));
}
vector<Point> GetHull() const {
vector<Point> points;
for (set< pair<double, Point> >::const_iterator p = hull.begin(); p != hull.end(); ++p)
points.push_back(p->second);
return points;
}
private:
set< pair<double, Point> > hull;
Point center;
static double Det(const Point &a, const Point &b, const Point &c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
double Alpha(const Point &p) const {
return atan2(p.y - center.y, p.x - center.x);
}
set< pair<double, Point> >::iterator Next(set< pair<double, Point> >::iterator p) const {
++p;
if (p == hull.end())
p = hull.begin();
return p;
}
set< pair<double, Point> >::iterator Previous(set< pair<double, Point> >::iterator p) const {
if (p == hull.begin())
p = hull.end();
--p;
return p;
}
};
int main() {
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in >> n;
vector<Point> points = vector<Point>(n);
for (int i = 0; i < n; ++i)
in >> points[i].x >> points[i].y;
vector<Point> hull = ConvexHull(points).GetHull();
out << int(hull.size()) << "\n";
for (int i = 0; i < int(hull.size()); ++i)
out << fixed << setprecision(9) << hull[i].x << " " << hull[i].y << "\n";
in.close();
out.close();
return 0;
}