Pagini recente » Cod sursa (job #2377687) | Cod sursa (job #2757867) | Cod sursa (job #2739908) | Cod sursa (job #2854886) | Cod sursa (job #2755459)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
const int NMAX = 12e4;
class Point {
public:
double x, y;
Point() = default;
};
Point a[1 + NMAX];
std::vector<int> stack;
inline double ccw(const Point& origin, const Point& A, const Point& B) {
double ax = A.x - origin.x;
double ay = A.y - origin.y;
double bx = B.x - origin.x;
double by = B.y - origin.y;
return ax * by - ay * bx;
}
inline double distSqr(const Point& A, const Point& B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
bool cmp_ccw(const Point& A, const Point& B) {
double _ccw = ccw(a[1], A, B);
/*
if (_ccw == 0)
return distSqr(a[1], A) < distSqr(a[1], B);
*/
return _ccw > 0;
}
int main() {
std::ifstream in("infasuratoare.in");
std::ofstream out("infasuratoare.out");
int n;
in >> n;
int minIdx = 1;
for (int i = 1; i <= n; ++i) {
in >> a[i].x >> a[i].y;
if (a[i].x < a[minIdx].x || (a[i].x == a[minIdx].x && a[i].y < a[minIdx].y))
minIdx = i;
}
std::swap(a[1], a[minIdx]);
std::sort(a + 2, a + 1 + n, cmp_ccw);
stack.reserve(n);
stack.push_back(1);
stack.push_back(2);
for (int i = 3; i <= n; ++i) {
while (stack.size() >= 2 && ccw(a[stack[stack.size() - 2]], a[stack[stack.size() - 1]], a[i]) <= 0)
stack.pop_back();
stack.push_back(i);
}
out << stack.size() << '\n';
for (auto& idx : stack)
out << std::fixed << std::setprecision(6) << a[idx].x << ' ' << a[idx].y << '\n';
return 0;
}