Pagini recente » Cod sursa (job #451947) | Cod sursa (job #2618946) | Cod sursa (job #1944670) | Cod sursa (job #839824) | Cod sursa (job #2220101)
/**
* Worg
*/
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define x first
#define y second
FILE *fin = freopen("infasuratoare.in", "r", stdin); FILE *fout = freopen("infasuratoare.out", "w", stdout);
typedef std::pair<double, double > Point;
/*-------- Data --------*/
int n;
std::vector<Point > points;
/*-------- --------*/
void ReadInput() {
scanf("%d", &n); points.resize(n);
for(auto& point : points) {
scanf("%lf%lf", &point.x, &point.y);
}
}
double CrossProduct(Point A, Point B, Point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
std::vector<Point > ConvexHull(std::vector<Point > &points) {
int n = (int)points.size();
for(int i = 1; i < n; i++) {
if(points[i] < points[0]) {
std::swap(points[0], points[i]);
}
}
std::sort(points.begin() + 1, points.end(), [&](Point &A, Point &B) {
return CrossProduct(points[0], A, B) > 0;
});
std::vector<Point > convexHull; convexHull.push_back(points[0]);
for(int i = 1; i < n; i++) {
auto point = points[i];
while(convexHull.size() > 1 && CrossProduct(convexHull[(int)convexHull.size() - 2], convexHull[(int)convexHull.size() - 1], point) < 0) {
convexHull.pop_back();
}
convexHull.push_back(point);
}
return convexHull;
}
int main() {
ReadInput();
auto convexHull = ConvexHull(points);
printf("%d\n", (int)convexHull.size());
for(auto& point : convexHull) {
printf("%.12f %.12f\n", point.x, point.y);
}
return 0;
}