Pagini recente » Statistici Oana A (OanaA) | Cod sursa (job #1369040) | Arhiva de probleme | Cod sursa (job #3221650) | Cod sursa (job #2202950)
#include <bits/stdc++.h>
const double kEps = 1e-6;
bool Equals(double a, double b) {
return fabs(a - b) < kEps;
}
struct Point {
Point() : x(0.0), y(0.0) {}
Point(double x, double y) : x(x), y(y) {}
double CrossProduct(const Point& b, const Point& c) const {
return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
}
double Distance(const Point& b, const Point& c) const {
return fabs((c.y - b.y) * x - (c.x - b.x) * y + c.x * b.y - c.y * b.x) /
sqrt((c.y - b.y) * (c.y - b.y) + (c.x - b.x) * (c.x - b.x));
}
bool InTriangle(const Point& a, const Point& b, const Point& c) const {
bool c1 = CrossProduct(a, b) < 0.0;
bool c2 = CrossProduct(b, c) < 0.0;
bool c3 = CrossProduct(c, a) < 0.0;
return (c1 == c2) && (c2 == c3);
}
bool operator == (const Point& b) const {
return Equals(x, b.x) && Equals(y, b.y);
}
bool operator != (const Point& b) const {
return !(*this == b);
}
double x, y;
};
std::vector<Point> ReadPoints(const std::string& input_file) {
std::ifstream fin(input_file);
int num_points;
fin >> num_points;
std::vector<Point> points;
for (int i = 0; i < num_points; i++) {
double x, y;
fin >> x >> y;
points.emplace_back(x, y);
}
return points;
}
std::vector<Point> SolveQuickHull(const Point& low_point,
const Point& high_point, const std::vector<Point>& candidates) {
if (candidates.empty()) {
return std::vector<Point>();
}
double best_distance = 0.0;
Point best_point;
for (const Point& point : candidates) {
double point_distance = point.Distance(low_point, high_point);
if (point_distance > best_distance) {
best_distance = point_distance;
best_point = point;
}
}
std::vector<Point> left_side;
std::vector<Point> right_side;
for (const Point& point : candidates) {
if (point != best_point) {
if (point.InTriangle(low_point, high_point, best_point)) {
continue;
}
if (point.CrossProduct(low_point, best_point) > 0) {
left_side.push_back(point);
} else {
right_side.push_back(point);
}
}
}
/* std::cout << best_point.x << " " << best_point.y << '\n'; */
/* for (auto it : left_side) { */
/* std::cout << it.x << " " << it.y << " "; */
/* } */
/* std::cout << '\n'; */
/* for (auto it : right_side) { */
/* std::cout << it.x << " " << it.y << " "; */
/* } */
/* std::cout << '\n'; */
/* std::cout << "------------------------\n"; */
std::vector<Point> left_convex_hull = SolveQuickHull(high_point, best_point,
left_side);
std::vector<Point> right_convex_hull = SolveQuickHull(low_point, best_point,
right_side);
std::vector<Point> convex_hull;
convex_hull.insert(convex_hull.end(), left_convex_hull.begin(),
left_convex_hull.end());
convex_hull.push_back(best_point);
convex_hull.insert(convex_hull.end(), right_convex_hull.begin(),
right_convex_hull.end());
return convex_hull;
}
std::vector<Point> QuickHull(const std::vector<Point>& points) {
int num_points = points.size();
Point low_point = *points.begin();
Point high_point = *points.begin();
for (const Point& point : points) {
if (point.y < low_point.y) {
low_point = point;
}
if (point.y > high_point.y) {
high_point = point;
}
}
std::vector<Point> left_side;
std::vector<Point> right_side;
for (const Point& point : points) {
if (point != low_point && point != high_point) {
double cross_product = point.CrossProduct(high_point, low_point);
if (Equals(cross_product, 0.0)) {
continue;
}
if (cross_product < 0) {
left_side.push_back(point);
} else {
right_side.push_back(point);
}
}
}
std::vector<Point> left_convex_hull = SolveQuickHull(low_point, high_point,
left_side);
std::vector<Point> right_convex_hull = SolveQuickHull(low_point, high_point,
right_side);
std::vector<Point> convex_hull;
convex_hull.insert(convex_hull.end(), left_convex_hull.begin(),
left_convex_hull.end());
convex_hull.push_back(high_point);
convex_hull.insert(convex_hull.end(), right_convex_hull.begin(),
right_convex_hull.end());
convex_hull.push_back(low_point);
return convex_hull;
}
int main(int argc, char** argv) {
/* if (argc != 2) { */
/* std::cout << "Usage: ./seq <input_file> <output_file>" << '\n'; */
/* exit(1); */
/* } */
/* auto points = ReadPoints(std::string(argv[1])); */
auto points = ReadPoints(std::string("infasuratoare.in"));
auto convex_hull = QuickHull(points);
std::ofstream fout("infasuratoare.out");
std::reverse(convex_hull.begin(), convex_hull.end());
fout << convex_hull.size() << '\n';
for (const Point& point : convex_hull) {
fout << std::fixed << std::setprecision(6)
<< point.x << " " << point.y << '\n';
}
return 0;
}