Pagini recente » Cod sursa (job #1664739) | Cod sursa (job #2337480) | Cod sursa (job #2455672) | Cod sursa (job #1938084) | Cod sursa (job #2858466)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#endif
struct Point {
ld x,y;
Point operator - (const Point other) const {
return {x - other.x , y - other.y};
}
bool operator < (const Point other) const {
///we want the left-most point, and the lowest one if possible
if (x != other.x) {
return x < other.x;
}
return y < other.y;
}
};
bool rightTurn(Point a, Point b, Point c) {
return b.x * c.y + c.x * a.y + a.x * b.y - b.x * a.y - c.x * b.y - a.x * c.y < 0;
}
vector<Point> pt;
int n;
vector<Point> res;
void convexHull() {
int leftLow = 1;
for (int i = 2; i <= n; i++) {
if (pt[i] < pt[leftLow]) {
leftLow = i;
}
}
swap(pt[1] , pt[leftLow]); // leftLow is the first one;
sort(pt.begin() + 2, pt.end() , [&](Point p1, Point p2) {
/// y / x < y2 / x2
p1 = p1 - pt[leftLow];
p2 = p2 - pt[leftLow];
return p1.y * p2.x < p2.y * p1.x;
});
for (int i = 1; i <= n; i++) {
int rs = (int)res.size();
while(rs >= 2 && rightTurn(res[rs - 2] , res[rs - 1] , pt[i])) {
res.pop_back();
rs = (int)res.size();
}
res.push_back(pt[i]);
}
}
int main() {
in >> n;
pt.resize(n + 1);
for (int i = 1; i <= n; i++) {
ld x,y;
in >> pt[i].x >> pt[i].y;
}
convexHull();
out << fixed << setprecision(12);
out << res.size() << "\n";
for (auto k : res) {
out << k.x << " " << k.y << "\n";
}
}