Pagini recente » Cod sursa (job #2960579) | Cod sursa (job #2516979) | Cod sursa (job #3283938) | Cod sursa (job #3037503) | Cod sursa (job #2846835)
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl
#define all(a) a.begin(), a.end()
#define range(a, l, r) a.begin() + l, a.begin() + r
#define aall(a, n) a + 1, a + 1 + n
#define arange(a, l, r) a + l, a + r
#define maxself(a, b) a = std::max(a, b);
#define minself(a, b) a = std::min(a, b);
#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
const int NMAX = 1.2e5;
class Point {
public:
long double x, y;
Point() = default;
};
int n;
Point a[1 + NMAX];
std::vector<int> stack;
inline long double ccw(const Point& origin, const Point &A, const Point &B) {
return (A.x - origin.x) * (B.y - origin.y) - (B.x - origin.x) * (A.y - origin.y);
}
bool ccwSort(const Point& i, const Point& j) {
return ccw(a[1], i, j) > 0;
}
int main() {
inout("infasuratoare");
in >> n;
int start = 1;
for (int i = 1; i <= n; ++i) {
in >> a[i].x >> a[i].y;
if (a[i].x < a[start].x || (a[i].x == a[start].x && a[i].y < a[start].y))
start = i;
}
std::swap(a[1], a[start]);
std::sort(arange(a, 2, 1 + n), ccwSort);
stack.push_back(1);
for (int i = 2; 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 (int i : stack)
out << std::fixed << std::setprecision(6) << a[i].x << ' ' << a[i].y << '\n';
return 0;
}