Pagini recente » Cod sursa (job #2933676) | Cod sursa (job #974604) | Cod sursa (job #2919656) | Cod sursa (job #2936033) | Cod sursa (job #2404041)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
int n;
struct point {
double x, y;
} P[N];
int st[N], last;
double determinant(const point &p0, const point &p1, const point &p2) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
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 convexHull() {
st[1] = 0;
st[2] = 1;
last = 2;
for (int i = 2; i < n; i++) {
double d = determinant(P[st[last - 1]], P[st[last]], P[i]);
if (d < 0) {
while (d < 0) {
last--;
d = determinant(P[st[last - 1]], P[st[last]], P[i]);
}
st[++last] = i;
} else if (d == 0)
st[last] = i;
else
st[++last] = i;
}
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
double xmin = DBL_MAX, ymin = DBL_MAX;
int extremum = 0;
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;
extremum = i;
}
}
swap(P[extremum], P[0]);
sort(P + 0, P + n, [](const point &a, const point &b) {
double det = determinant(P[0], a, b);
return det > 0 || (det == 0 && dist(P[0], a) < dist(P[0], b));
});
convexHull();
cout << last << '\n';
for (int i = 1; i <= last; i++)
cout << fixed << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << '\n';
return 0;
}