Pagini recente » Cod sursa (job #1112526) | Cod sursa (job #571011) | Cod sursa (job #1023559) | Cod sursa (job #636855) | Cod sursa (job #2950507)
#include <bits/stdc++.h>
#define MAXN 120000
struct Point{
double x;
double y;
};
bool cmpXy(Point A, Point B){return (A.x < B.x || (A.x == B.x && A.y < B.y));}
bool convex(Point a, Point b, Point c){
float S = (a.x * b.y + b.x * c.y + c.x * a.y) -
(a.x * c.y + b.x * a.y + c.x * b.y);
return S;
}
std::vector<Point> upper_hull(const std::vector<Point>& v) {
int last = 1;
std::vector<Point> S {v[0], v[1]};
for(int i = 2; i < v.size(); i++){
while(convex(S[last - 1], S[last], v[i]) < 0)
last--, S.pop_back();
last++, S.push_back(v[i]);
}
return S;
}
std::vector<Point> lower_hull(const std::vector<Point>& v) {
int last = 1;
std::vector<Point> S {v[0], v[1]};
for(int i = 2; i < v.size(); i++){
while(convex(S[last - 1], S[last], v[i]) > 0)
last--, S.pop_back();
last++, S.push_back(v[i]);
}
return S;
}
int main(){
FILE*fi,*fo;
fi = fopen("hull.in","r");
fo = fopen("hull.out","w");
int n;
fscanf(fi,"%d", &n);
std::vector<Point> v;
for(int i = 1; i <= n; i++) {
double x, y;
fscanf(fi,"%lf%lf", &x, &y);
v.push_back({x, y});
}
std::sort(v.begin(), v.end(), cmpXy);
auto upper = upper_hull(v);
auto lower = lower_hull(v);
fprintf(fo, "%lu\n", lower.size() + upper.size() - 1);
for(int i = 0; i < (int) lower.size(); i++) {
const auto& [x, y] = lower[i];
fprintf(fo,"%f %f\n", x, y);
}
for(int i = (int) upper.size() - 2; i >= 0; i--) {
const auto& [x, y] = upper[i];
fprintf(fo,"%f %f\n", x, y);
}
return 0;
}