Pagini recente » Borderou de evaluare (job #2665399) | Borderou de evaluare (job #3228029) | Borderou de evaluare (job #3255519) | Borderou de evaluare (job #149743) | Cod sursa (job #2462811)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
struct point {
double x, y;
} p[N];
vector<int> selectedPoints;
int n;
double det(const point &o, const point &a, const point &b) {
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
double dist(const point &a, const point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
void convex_hull() {
selectedPoints.push_back(0);
selectedPoints.push_back(1);
int t = 1;
for (int i = 2; i < n; i++) {
double d = det(p[selectedPoints[t - 1]], p[selectedPoints[t]], p[i]);
if (d > 0)
selectedPoints.push_back(i), t++;
else if (d == 0)
*selectedPoints.rbegin() = i;
else {
while (d < 0) {
selectedPoints.pop_back();
t--;
d = det(p[selectedPoints[t - 1]], p[selectedPoints[t]], p[i]);
}
selectedPoints.push_back(i);
t++;
}
}
}
int main() {
ifstream cin ( "infasuratoare.in");
ofstream cout ("infasuratoare.out");
cin >> n;
double xMin = DBL_MAX, yMin = DBL_MAX;
int refPoint;
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y;
if (p[i].y < yMin || (p[i].y == yMin && p[i].x < xMin))
xMin = p[i].x, yMin = p[i].y, refPoint = i;
}
swap(p[refPoint], p[0]);
sort(p + 1, p + n, [](const point &a, const point &b) {
double d = det(p[0], a, b);
return d > 0 || (d == 0 && dist(p[0], a) < dist(p[0], b));
});
convex_hull();
cout << selectedPoints.size();
for (int i : selectedPoints)
cout << fixed << setprecision(6) << '\n' << p[i].x << " " << p[i].y;
return 0;
}