Pagini recente » Cod sursa (job #1866984) | Cod sursa (job #598566) | Cod sursa (job #1504440) | Cod sursa (job #1106872) | Cod sursa (job #3041349)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int,int>;
#define eb emplace_back
const string TASK("infasuratoare");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
const int N = 120000 + 5;
struct Point {ld x, y;} v[N];
ld prod(Point& o, Point& a, Point& b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool cmp(Point& a, Point& b) {
return prod(v[1], a, b) < 0;
}
int n, head;
Point hull[N];
int32_t main() {
fin >> n;
int pos = 1;
for (int i = 1; i <= n; ++i) {
fin >> v[i].x >> v[i].y;
if (make_pair(v[i].x,v[i].y) < make_pair(v[pos].x,v[pos].y))
pos = i;
}
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
hull[1] = v[1];
hull[2] = v[2];
head = 2;
for (int i = 3; i <= n; ++i) {
while (head >= 2 && prod(hull[head-1], hull[head], v[i]) > 0)
--head;
hull[++head] = v[i];
}
fout << fixed;
fout << head << '\n';
for (int i = head; i > 0; --i)
fout << setprecision(9) << hull[i].x << ' ' << hull[i].y << '\n';
}