Pagini recente » Cod sursa (job #2346787) | Cod sursa (job #1827863) | Cod sursa (job #1409317) | Cod sursa (job #174863) | Cod sursa (job #2672362)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
struct point {
ld x, y;
bool operator < (const point& oth) {
if (x == oth.x)
return y < oth.y;
return x < oth.x;
}
};
ld det(point p1, point p2, point p3) {
return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y -
p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
vector < point > v(n);
for (auto& it : v)
cin >> it.x >> it.y;
int pos_min = min_element(v.begin(), v.end()) - v.begin();
swap(v[pos_min], v[0]);
sort(v.begin() + 1, v.end(), [&](const point& p1, const point& p2) {
return (p1.x - v[0].x) * (p2.y - v[0].y) > (p1.y - v[0].y) * (p2.x - v[0].x);
});
vector < point > stack(n + 5);
int top_stack = 1;
stack[0] = v[0]; stack[1] = v[1];
for (int i = 2; i < n; ++i) {
while (top_stack > 0 and det(stack[top_stack - 1], v[i], stack[top_stack]) > 0)
--top_stack;
stack[++top_stack] = v[i];
}
cout << top_stack + 1 << '\n';
for (int i = 0; i <= top_stack; ++i)
cout << fixed << setprecision(12) << stack[i].x << ' ' << stack[i].y << '\n';
return 0;
}