Pagini recente » Cod sursa (job #2643475) | Cod sursa (job #2627254) | Cod sursa (job #2625214) | Cod sursa (job #2421481) | Cod sursa (job #3141707)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, viz[10001];
struct coord {
long double x, y;
} v[10001], S[10001], D[10001];
bool cmp (coord a, coord b) {
if (a.x > b.x) {
return 0;
}
if (a.x == b.x) {
if (a.y > b.y) {
return 0;
}
return 1;
}
return 1;
}
int main () {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + 1 + n, cmp);
int cnt = 2;
S[1].x = v[1].x;
S[1].y = v[1].y;
S[2].x = v[2].x;
S[2].y = v[2].y;
for (int i = 3; i <= n; i++) {
//punctul A : S[cnt -1].x, S[cnt - 1].y
//punctul B : S[cnt].x, S[cnt].y
//punctul C : v[i].x, v[i].y
while (cnt >= 2 && (v[i].y - S[cnt - 1].y) * (S[cnt].x - S[cnt - 1].x) - (S[cnt].y - S[cnt - 1].y) * (v[i].x - S[cnt - 1].x) < 0) {
cnt--;
}
cnt++;
S[cnt].x = v[i].x;
S[cnt].y = v[i].y;
}
int cnt2 = 2;
D[1].x = v[n].x;
D[1].y = v[n].y;
D[2].x = v[n - 1].x;
D[2].y = v[n - 1].y;
for (int i = n - 2; i >= 1; i--) {
//punctul A : D[cnt -1].x, D[cnt - 1].y
//punctul B : D[cnt].x, D[cnt].y
//punctul C : v[i].x, v[i].y
while (cnt2 >= 2 && (v[i].y - D[cnt2 - 1].y) * (D[cnt2].x - D[cnt2 - 1].x) - (D[cnt2].y - D[cnt2 - 1].y) * (v[i].x - D[cnt2 - 1].x) < 0) {
cnt2--;
}
cnt2++;
D[cnt2].x = v[i].x;
D[cnt2].y = v[i].y;
}
fout << cnt + cnt2 - 2 << '\n';
for (int i = 1; i <= cnt; i++) {
fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << '\n';
}
for (int i = 1; i <= cnt2; i++) {
if (D[i].x == v[1].x && D[i].y == v[1].y) {
continue;
} else if (D[i].x == v[n].x && D[i].y == v[n].y) {
continue;
} else {
fout << fixed << setprecision(6) << D[i].x << " " << D[i].y << '\n';
}
}
return 0;
}