Pagini recente » Cod sursa (job #3270731) | Cod sursa (job #2781968)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define vector vector1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1
typedef long double ld;
class vector {
public:
ld x;
ld y;
vector(ld x, ld y) : x(x), y(y) {
}
vector() {
}
};
const ld eps = 1e-14;
vector operator - (vector a) {
return vector(-a.x, -a.y);
}
vector operator - (vector a, vector b) {
return vector(a.x - b.x, a.y - b.y);
}
vector perpendicular(vector a) {
return vector(-a.y, a.x);
}
ld dot(vector a, vector b) {
return a.x * b.x + a.y * b.y;
}
ld cross(vector a, vector b) {
return a.y * b.x - a.x * b.y;
}
int getSign(ld value) {
if (abs(value) < eps) {
return 0;
}
if (value >= -eps) {
return 1;
} else {
return -1;
}
}
ld paralelogram(vector a, vector b, vector c) {
return cross(b - a, c - a);
}
const int N = 120000 + 7;
int n;
vector a[N];
vector stk[N];
int sz;
bool cmp(vector ff, vector ss) {
return getSign(paralelogram(a[1], ff, ss)) == -1;
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
if (a[i].x < a[1].x || (a[i].x == a[1].x && a[i].y < a[1].y)) swap(a[i], a[1]);
}
sort(a + 2, a + n + 1, cmp);
a[n + 1] = a[1];
for (int i = 1; i <= n + 1; i++) {
vector pt = a[i];
while (sz >= 2 && getSign(paralelogram(stk[sz - 1], stk[sz], pt)) >= 0) {
sz--;
}
stk[++sz] = pt;
}
sz--;
cout << sz << "\n";
for (int i = 1; i <= sz; i++) {
cout << fixed << setprecision(12) << stk[i].x << " " << stk[i].y << "\n";
}
return 0;
}