Pagini recente » Cod sursa (job #2397530) | Cod sursa (job #1029642) | Cod sursa (job #1682801) | Cod sursa (job #1898897) | Cod sursa (job #1165638)
#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(atan2(points[i].y - center.y, points[i].x - center.x), points[i]));
for (int i = 3; i < int(points.size()); ++i)
Insert(points[i]);
}
void Insert(const Point &p) {
double alpha = atan2(p.y - center.y, p.x - center.x);
set< pair<double, Point> >::iterator after = hull.lower_bound(make_pair(alpha, p)), before;
if (after == hull.end())
after = hull.begin();
before = Previous(after);
if (Det(before->second, p, after->second) < EPS)
return;
while (int(hull.size()) > 2 && Det(p, after->second, Next(after)->second) < EPS) {
hull.erase(after);
after = hull.lower_bound(make_pair(alpha, p));
if (after == hull.end())
after = hull.begin();
}
before = Previous(after);
while (int(hull.size()) > 2 && Det(Previous(before)->second, before->second, p) < EPS) {
hull.erase(before);
before = hull.lower_bound(make_pair(alpha, p));
if (before == hull.begin())
before = hull.end();
--before;
}
hull.insert(make_pair(alpha, p));
}
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;
}
static double Det(const Point &a, const Point &b, const Point &c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
private:
set< pair<double, Point> > hull;
Point center;
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;
}
};
vector<Point> Points, Hull;
void Solve() {
Hull = ConvexHull(Points).GetHull();
}
void Read() {
ifstream cin("infasuratoare.in");
int n;
cin >> n;
Points = vector<Point>(n);
for (int i = 0; i < n; ++i)
cin >> Points[i].x >> Points[i].y;
cin.close();
}
void Print() {
ofstream cout("infasuratoare.out");
cout << int(Hull.size()) << "\n";
for (int i = 0; i < int(Hull.size()); ++i)
cout << fixed << setprecision(7) << Hull[i].x << " " << Hull[i].y << "\n";
cout.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}