Pagini recente » Cod sursa (job #2641465) | Cod sursa (job #2543034) | Cod sursa (job #360208) | Cod sursa (job #1162534) | Cod sursa (job #2781969)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long double ld;
class ve {
public:
ld x;
ld y;
ve(ld x, ld y) : x(x), y(y) {
}
ve() {
}
};
const ld eps = 1e-14;
ve operator - (ve a) {
return ve(-a.x, -a.y);
}
ve operator - (ve a, ve b) {
return ve(a.x - b.x, a.y - b.y);
}
ve perpendicular(ve a) {
return ve(-a.y, a.x);
}
ld dot(ve a, ve b) {
return a.x * b.x + a.y * b.y;
}
ld cross(ve a, ve 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(ve a, ve b, ve c) {
return cross(b - a, c - a);
}
const int N = 120000 + 7;
int n;
ve a[N];
ve stk[N];
int sz;
bool cmp(ve ff, ve 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++) {
ve 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;
}