Pagini recente » Cod sursa (job #880778) | Cod sursa (job #548538) | Cod sursa (job #1129895) | Cod sursa (job #1614201) | Cod sursa (job #2238817)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <double, double> Point;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
double crossProduct (const Point &a, const Point &b, const Point &c) {
return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); // mut punctele a.i. a sa fie in (0, 0)
}
const int NMAX = 12e4 + 5;
Point v[NMAX];
int n;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif
g.precision (6);
g << fixed;
f >> n;
for (int i = 1; i <= n; ++i) f >> v[i].fi >> v[i].se;
int pos = 1;
for (int i = 2; i <= n; ++i) {
if (v[i] < v[pos]) {
pos = i;
}
}
swap (v[1], v[pos]);
sort (v + 2, v + 1 + n, [] (const Point &a, const Point &b) {
return (crossProduct (v[1], a, b) < 0);
});
vi stk;
int top = 1;
stk.pb (1);
stk.pb (2);
for (int i = 3; i <= n; ++i) {
while (top >= 1 && crossProduct (v[stk[top - 1]], v[i], v[stk[top]]) < 0) {
--top;
stk.pop_back();
}
stk.pb (i);
++top;
}
g << top + 1 << '\n';
reverse (all (stk));
for (int &i : stk) {
g << v[i].fi << ' ' << v[i].se << '\n';
}
}