Pagini recente » Cod sursa (job #1334175) | Cod sursa (job #16580) | Cod sursa (job #1415512) | Cod sursa (job #1337672) | Cod sursa (job #1178396)
#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;
inline 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);
}
class Compare {
public:
static vector<double> alpha;
bool operator()(const int a, const int b) const {
return alpha[a] < alpha[b];
}
};
vector<double> Compare::alpha = vector<double>();
vector<int> ConvexHull(const vector<Point> &points) {
int n = int(points.size());
int center = 0;
for (int i = 1; i < n; ++i)
if (points[i] < points[center])
center = i;
vector<double> alpha = vector<double>(n);
for (int i = 0; i < n; ++i)
alpha[i] = atan2(points[i].y - points[center].y, points[i].x - points[center].x);
vector<int> index = vector<int>(n);
for (int i = 0; i < n; ++i)
index[i] = i;
swap(index[0], index[center]);
Compare::alpha = alpha;
sort(index.begin() + 1, index.end(), Compare());
vector<int> hull;
hull.push_back(index[0]);
hull.push_back(index[1]);
for (int i = 2; i < n; ++i) {
while (int(hull.size()) > 1 && Det(points[hull[int(hull.size()) - 2]], points[hull.back()], points[index[i]]) < -EPS)
hull.pop_back();
hull.push_back(index[i]);
}
return hull;
}
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<int> hull = ConvexHull(points);
out << int(hull.size()) << "\n";
for (int i = 0; i < int(hull.size()); ++i)
out << fixed << setprecision(9) << points[hull[i]].x << " " << points[hull[i]].y << "\n";
in.close();
out.close();
return 0;
}