Pagini recente » Cod sursa (job #1213924) | Cod sursa (job #2154005) | Cod sursa (job #2147321) | Cod sursa (job #2671474) | Cod sursa (job #2552949)
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct point {
double x, 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 };
double roll(double low, double high, double increments, double val) {
if (val < low)
return roll(low, high, increments, val + increments);
if (val >= high)
return roll(low, high, increments, val - increments);
return val;
}
double atan2deg(double x, double y) {
if (x == 0 && y == 0)
return -180;
return atan2(y, x) * 180 / M_PI;
}
double deg(point a, point b, point c) {
return roll(0, 360, 360, atan2deg(a.x - b.x, a.y - b.y) - atan2deg(c.x - b.x, c.y - b.y));
}
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 atan2deg(l.x - firstPoint.x, l.y - firstPoint.y) < atan2deg(r.x - firstPoint.x, r.y - firstPoint.y);
});
deque<point> s;
s.push_back(v[1]);
s.push_back(v[2]);
for (int i = 3; i <= n; i++) {
while (s.size() >= 2 && abs(deg(s[s.size() - 2], s[s.size() - 1], v[i])) > 180) {
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();
}
}