Pagini recente » Cod sursa (job #1512951) | Cod sursa (job #2109688) | Cod sursa (job #1519308) | Cod sursa (job #1954154) | Cod sursa (job #2971180)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif
#define endl '\n'
const int NMAX = 120005;
struct Point {
double x, y;
bool operator==(const Point &p) {
return x == p.x && y == p.y;
}
};
int n;
Point a[NMAX];
vector<int> st;
inline double det(const Point &a, const Point &b, const Point &c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
void read() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i].x >> a[i].y;
}
}
int cmp(const Point &a, const Point &b) {
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
void solve() {
st = {1, 2};
for (int i = 3; i <= n; i++) {
if (st.back() == a[i]) continue;
while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) < 0) {
st.pop_back();
}
st.push_back(i);
}
for (int i = n - 1; i >= 1; i--) {
if (st.back() == a[i]) continue;
while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) < 0) {
st.pop_back();
}
st.push_back(i);
}
fout << st.size() - 1 << endl;
for (int i = 0; i < st.size() - 1; i++) {
fout << setprecision(12) << fixed << a[st[i]].x << ' ' << a[st[i]].y << endl;
}
}
int main() {
read();
sort(a + 1, a + n + 1, cmp);
solve();
return 0;
}