Pagini recente » Cod sursa (job #2919853) | Cod sursa (job #1993842) | Cod sursa (job #2267708) | Cod sursa (job #854503) | Cod sursa (job #2714207)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<double, double> Point;
inline double cross_product(Point O, Point A, Point B) {
return (A.first - O.first) * (B.second - O.second)
- (B.first - O.first) * (A.second - O.second);
}
int main() {
FILE * f;
int n;
f = fopen("infasuratoare.in", "r");
fscanf(f, "%d", &n);
vector<Point> points(n);
int min_pos = 0;
for (int i = 0; i < n; ++i) {
fscanf(f, "%lf%lf", &points[i].first, &points[i].second);
if (points[i] < points[min_pos]) {
min_pos = i;
}
}
fclose(f);
/*
* sort the points in clockwise order by the polar angle
* made with the point that has the lowest coordinates
*/
swap(points[0], points[min_pos]);
sort(
points.begin() + 1,
points.end(),
[&](Point A, Point B) {return cross_product(points[0], A, B) < 0;}
);
vector<Point> convex_hull(n);
convex_hull[0] = points[0];
convex_hull[1] = points[1];
int hull_size = 1;
for (int i = 2; i < n; ++i) {
while (
hull_size >= 1 &&
cross_product(convex_hull[hull_size - 1], convex_hull[hull_size], points[i]) >= 0
) {
--hull_size;
}
++hull_size;
convex_hull[hull_size] = points[i];
}
f = fopen("infasuratoare.out", "w");
fprintf(f, "%d\n", hull_size + 1);
while (hull_size >= 0) {
fprintf(f, "%.6lf %.6lf\n", convex_hull[hull_size].first, convex_hull[hull_size].second);
--hull_size;
}
fclose(f);
return 0;
}