Pagini recente » Cod sursa (job #1189069) | Cod sursa (job #2336974) | Cod sursa (job #287579) | Cod sursa (job #677079) | Cod sursa (job #2227564)
#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) >= 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;
}