Pagini recente » Cod sursa (job #2282471) | Cod sursa (job #1183963) | Cod sursa (job #1055525) | Cod sursa (job #228330) | Cod sursa (job #2227562)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
struct Point{
double x = 0;
double y = 0;
double angle(const Point& other) const{
return std::atan2(other.y - y, other.x - x);
}
};
inline std::istream& operator >>(std::istream& in, Point& p)
{
in >> p.x >> p.y;
return in;
}
double ccw(const Point& p1, const Point& p2, const Point& p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int main()
{
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int N;
std::vector<Point> points;
fin >> N;
Point best;
bool first = true;
for (int i = 0; i < N; ++i) {
Point p;
fin >> p;
if (first||(p.x <= best.x && p.y <= best.y)) {
if(!first) {
points.push_back(best);
}
best = p;
} else {
points.push_back(p);
}
first = false;
}
const auto cmp = [&best](const Point& lhs, const Point& rhs)->bool {return best.angle(lhs) < best.angle(rhs);};
std::sort(points.begin(), points.end(),cmp);
std::vector<Point> hull;
hull.push_back(best);
for(const auto& p : points) {
if (hull.size() < 2) {
hull.push_back(p);
} else {
bool positiveDotProd = false;
do {
const auto& P2 = hull.back();
const auto& P1 = *(hull.rbegin() + 1);
positiveDotProd = ccw(P1, P2, p) >= 1e-12;
if (!positiveDotProd) {
hull.pop_back();
}
} while(!positiveDotProd && hull.size() >= 2);
hull.push_back(p);
}
}
fout << hull.size() << "\n";
fout << std::setprecision(6) << std::fixed;
for (const auto& p : hull) {
fout << p.x << " " << p.y << "\n";
}
return 0;
}