Pagini recente » Cod sursa (job #750357) | Cod sursa (job #1029574) | Cod sursa (job #738079) | Cod sursa (job #658727) | Cod sursa (job #1837103)
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 121000;
int n;
pair <double, double> p[NMAX];
inline int Cross(int i, int j, int k) {
double fi = (p[j].fi - p[i].fi) * (p[k].se - p[i].se);
double se = (p[k].fi - p[i].fi) * (p[j].se - p[i].se);
return (fi == se ? 0 : (fi < se ? -1 : 1));
}
int s[NMAX];
int ss;
vector <int> Convex(int l, int r) {
vector <int> c;
ss = 0;
for (int i = l; i <= r; i++) {
while (ss >= 2 && Cross(s[ss - 2], s[ss - 1], i) <= 0) {
ss--;
}
s[ss++] = i;
}
for (int i = 0; i < ss - 1; i++) {
c.push_back(s[i]);
}
ss = 0;
for (int i = r; i >= l; i--) {
while (ss >= 2 && Cross(s[ss - 2], s[ss - 1], i) <= 0) {
ss--;
}
s[ss++] = i;
}
for (int i = 0; i < ss - 1; i++) {
c.push_back(s[i]);
}
return c;
}
int main() {
f >> n;
for (int i = 1; i <= n; i++) {
f >> p[i].fi >> p[i].se;
}
sort(p + 1, p + n + 1);
vector <int> c = Convex(1, n);
g << c.size() << "\n";
g << setprecision(12) << fixed;
for (int i: c) {
g << p[i].fi << " " << p[i].se << "\n";
}
}