Pagini recente » Cod sursa (job #247489) | Cod sursa (job #2962497) | Cod sursa (job #1448157) | Cod sursa (job #2096430) | Cod sursa (job #3246557)
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int MAX = 120005;
struct ura {
float x, y;
} v[MAX];
int s[MAX], ns = 0, s2[MAX], ns2 = 0;
bool verif_jos(int i, int xa, int ya, int xb, int yb) {
int xc = v[i].x, yc = v[i].y;
return (xa * yb + xb * yc + xc * ya) < (ya * xb + yb * xc + yc * xa);
}
bool cmp(ura a, ura b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
float xa = v[1].x, ya = v[1].y, xb = v[n].x, yb = v[n].y;
s[++ns] = 1;
for (int i = 2; i <= n; i++) {
while (ns > 1 && verif_jos(i, v[s[ns - 1]].x, v[s[ns - 1]].y, v[s[ns]].x, v[s[ns]].y)) {
ns--;
}
s[++ns] = i;
}
s2[++ns2] = n;
for (int i = n - 1; i >= 1; i--) {
while (ns2 > 1 && !verif_jos(i, v[s2[ns2 - 1]].x, v[s2[ns2 - 1]].y, v[s2[ns2]].x, v[s2[ns2]].y)) {
ns2--;
}
s2[++ns2] = i;
}
cout << ns + ns2 - 2 << '\n';
cout << fixed << setprecision(6);
for (int i = 1; i <= ns; i++) {
cout << v[s[i]].x << " " << v[s[i]].y << '\n';
}
for (int i = 2; i < ns2; i++) {
cout << v[s2[i]].x << " " << v[s2[i]].y << '\n';
}
return 0;
}