Pagini recente » Cod sursa (job #582455) | Cod sursa (job #2321009) | Cod sursa (job #623617) | Cod sursa (job #3285304) | Cod sursa (job #2560824)
#pragma GCC optimize("O3")
#include <fstream>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct point {
double x, y;
double slope() {
if (x == 0 && y == 0)
return -1e158;
return y / x;
}
};
point operator+ (point a, point b) {
return { a.x + b.x, a.y + b.y };
}
point operator-(point a, point b) {
return { a.x - b.x, a.y - b.y };
}
ostream& operator<< (ostream& os, point& p) {
os << '(' << p.x << ',' << p.y << ')';
return os;
}
bool operator< (const point l, const point r) {
return l.x == r.x ? l.y < r.y : l.x < r.x;
}
point v[120005];
point firstPoint = { 1e30, 1e30 };
bool isDr(point a, point b, point c) {
return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x) < 0;
}
int main() {
in >> n;
out << fixed << setprecision(6);
for (int i = 1; i <= n; i++) {
in >> v[i].x >> v[i].y;
firstPoint = min(firstPoint, v[i]);
}
sort(v + 1, v + n + 1, [](const point& l, const point& r) {
return (l - firstPoint).slope() < (r - firstPoint).slope();
});
deque<point> s;
s.push_back(v[1]);
s.push_back(v[2]);
for (int i = 3; i <= n; i++) {
while (s.size() >= 2 && isDr(s[s.size() - 2], s[s.size() - 1], v[i])) {
s.pop_back();
}
s.push_back(v[i]);
}
out << s.size() << '\n';
while (!s.empty()) {
out << s.front().x << ' ' << s.front().y << '\n';
s.pop_front();
}
}