Pagini recente » Cod sursa (job #98869) | Cod sursa (job #2019084) | Cod sursa (job #543751) | Cod sursa (job #713262) | Cod sursa (job #2227569)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
struct Point{
double x = 0;
double y = 0;
};
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);
}
inline std::istream& operator >>(std::istream& in, Point& p)
{
in >> p.x >> p.y;
return in;
}
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 ccw(best, lhs, rhs) < 0;};
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) > 0;
if (positiveDotProd) {
hull.pop_back();
}
} while(positiveDotProd && hull.size() >= 2);
hull.push_back(p);
}
}
fout << hull.size() << "\n";
fout << std::setprecision(9) << std::fixed;
for (auto p = hull.rbegin(); p != hull.rend(); ++p) {
fout << p->x << " " << p->y << "\n";
}
return 0;
}