Pagini recente » Cod sursa (job #2841383) | Cod sursa (job #2045697) | Cod sursa (job #1124313) | Cod sursa (job #3236232) | Cod sursa (job #2574944)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX_N = 2e5 + 5;
struct Point {
long double x, y;
};
int n, k;
Point v[MAX_N];
int st[MAX_N];
long double f(Point a, Point b, Point c) {
return (a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y);
}
bool operator < (const Point &a, const Point &b) {
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
bool compare (const Point &a, const Point &b) {
return (f(v[0], a, b) < 0);
}
int main() {
int p;
fin >> n;
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
p = 0;
for (int i = 1; i < n; ++i) {
if (v[i] < v[p]) {
p = i;
}
}
swap(v[0], v[p]);
sort(v + 1, v + n, compare);
st[1] = 0;
st[2] = 1;
k = 2;
for (int i = 2; i < n; ++i) {
while (k > 1 && f(v[st[k - 1]], v[st[k]], v[i]) > 0) {
--k;
}
st[++k] = i;
}
fout << k << "\n";
for (int i = k; i > 0; --i) {
fout << fixed << setprecision(13) << v[st[i]].x << " " << v[st[i]].y << "\n";
}
return 0;
}