Pagini recente » Cod sursa (job #311617) | Cod sursa (job #1606174) | Cod sursa (job #612487) | Cod sursa (job #429715) | Cod sursa (job #1512613)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
typedef pair<double, double> point;
int n;
vector<point> v;
double cross_product(const point &O, const point &A, const point &B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
class my_stack : public stack<int> {
public:
int top_second() {
int x = top();
pop();
int result = top();
push(x);
return result;
}
};
int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#else
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#endif // LOCAL
cin >> n;
int pos;
point X = {INF, INF};
for (int i = 0; i < n; ++i) {
double x, y;
cin >> x >> y;
if (X.x > x || (X.x == x && X.y > y)) {
X = {x, y};
pos = i;
}
v.push_back({x, y});
}
swap(v[0], v[pos]);
sort(v.begin() + 1, v.end(), [X](const point &A, const point &B) {
return cross_product(X, A, B) < 0;
});
my_stack st;
st.push(0);
st.push(1);
for (int i = 2; i < n; ++i) {
if (st.size() >= 2 && cross_product(v[st.top_second()], v[st.top()], v[i]) > 0) {
st.pop();
}
st.push(i);
}
cout << st.size() << '\n';
cout << fixed << setprecision(6);
while (!st.empty()) {
point p = v[st.top()];
st.pop();
cout << p.x << ' ' << p.y << '\n';
}
return 0;
}