Pagini recente » Cod sursa (job #3196490) | Cod sursa (job #1925628) | Cod sursa (job #2403398) | Cod sursa (job #2236248) | Cod sursa (job #1307220)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <tuple>
#include <vector>
#include <iomanip>
using namespace std;
typedef pair<long double, long double> point_t;
inline
long double cosinus(const point_t& o, const point_t& p) {
return (p.first - o.first) /
sqrt((p.second - o.second)*(p.second - o.second) +
(p.first - o.first)*(p.first - o.first));
}
inline
bool isCCW(const point_t& a, const point_t& b, const point_t& c) {
return (b.first - a.first)*(c.second - a.second) -
(b.second - a.second)*(c.first - a.first) >= 0;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n; fin >> n;
vector<point_t> points;
for (long double x, y; fin >> x >> y;) points.push_back({x, y});
// choose "lowest-leftmost" point as the origin
for (auto& p : points)
if (p.second < points[0].second ||
(p.second == points[0].second && p.first < points[0].first))
swap(points[0], p);
{ // sorting is done using the cosine of the points to the origin
point_t origin = points[0];
sort(points.begin() + 1, points.end(),
[origin] (const point_t& a, const point_t& b) {
return cosinus(origin, a) >= cosinus(origin, b);
});
}
vector<point_t> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for (int i = 2; i < n; ++i) {
while (hull.size() > 2 && !isCCW(hull[hull.size() - 2], hull.back(), points[i]))
hull.pop_back();
hull.push_back(points[i]);
}
while (hull.size() > 3 && !isCCW(hull[hull.size() - 2], hull.back(), points[0]))
hull.pop_back();
fout << hull.size() << '\n';
for (auto p : hull)
fout << setprecision(12) << p.first << ' ' << p.second << '\n';
return 0;
}