Pagini recente » Cod sursa (job #1516265) | Cod sursa (job #1791420) | Cod sursa (job #2580027) | Cod sursa (job #92074) | Cod sursa (job #2781983)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <cassert>
#include <vector>
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);
}
bool operator < (ve a, ve b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool sub(set<ve> &hull, ve pt) {
auto it = hull.lower_bound(pt);
if (it == hull.end()) {
return 0;
}
if (it == hull.begin()) {
return (it->x == pt.x);
}
ve nxt = *it;
it--;
ve ant = *it;
return getSign(paralelogram(ant, nxt, pt)) == +1;
}
bool concav(set<ve> &hull, set<ve>::iterator it) {
if (it == hull.begin() || it == hull.end()) return 0;
ve now = *it;
it--;
ve ant = *it;
it++;
it++;
if (it == hull.end()) return 0;
ve nxt = *it;
return getSign(paralelogram(ant, now, nxt)) == -1;
}
void ins(set<ve> &hull, ve pt) {
if (sub(hull, pt)) return;
hull.insert(pt);
auto it = hull.find(pt);
it++;
while (concav(hull, it)) {
ve now = *it;
it++;
hull.erase(now);
}
it = hull.find(pt);
assert(it != hull.end());
if (it != hull.begin()) {
it--;
}
while (concav(hull, it)) {
ve now = *it;
it--;
hull.erase(now);
}
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
//cout << fixed << setprecision(12);
set<ve> low, high;
int n;
cin >> n;
while (n--) {
ve pt;
cin >> pt.x >> pt.y;
ins(low, pt);
ins(high, -pt);
}
// return 0;
vector<ve> a, b;
for (auto &it : low) {
a.push_back(it);
}
for (auto &it : high) {
b.push_back(-it);
}
b.pop_back();
reverse(b.begin(), b.end());
if (!b.empty() && a.back().x == b[0].x && a.back().y == b[0].y) {
b.pop_back();
}
vector<ve> all;
for (auto &it : a) {
all.push_back(it);
}
for (auto &it : b) {
all.push_back(it);
}
reverse(all.begin(), all.end());
cout << (int) all.size() << "\n";
for (auto &it : all) {
cout << fixed << setprecision(12) << it.x << " " << it.y << "\n";
}
return 0;
}