Pagini recente » Cod sursa (job #410002) | Cod sursa (job #2227734) | Cod sursa (job #2190887) | Cod sursa (job #819535) | Cod sursa (job #2461480)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
typedef pair < double, double > pi;
int n;
pi v[150000];
inline double cp(const pi& a, const pi& b, const pi& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline double cmp(const pi &p1, const pi &p2) {
return cp(v[1], p1, p2) < 0;
}
void graham() {
pi st[150000];
st[1] = v[1];
st[2] = v[2];
int h = 2;
for (int i = 3; i <= n; i++) {
while(h >= 2 && cp(st[h - 1], st[h], v[i]) > 0) --h;
st[++h] = v[i];
}
cout << h << "\n";
for (int i = h; i >= 1; i--) cout << fixed << setprecision(9) << st[i].x << " " << st[i].y << "\n";
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
}
int ind = 1;
for (int i = 2; i <= n; i++) if (v[i] < v[ind]) ind = i;
swap(v[1], v[ind]);
sort(v + 2, v + n + 1, cmp);
graham();
}