Created
December 18, 2019 22:45
-
-
Save vasalf/2d27c2a59cacf7ba165e54102478ed15 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <iostream> | |
#include <vector> | |
#include <boost/polygon/voronoi.hpp> | |
using namespace std; | |
using boost::polygon::voronoi_diagram; | |
using boost::polygon::voronoi_builder; | |
using boost::polygon::construct_voronoi; | |
typedef double ld; | |
struct point { | |
ld x, y; | |
point() {} | |
point(ld x_, ld y_) | |
: x(x_) | |
, y(y_) | |
{} | |
}; | |
namespace boost { | |
namespace polygon { | |
template<> | |
struct geometry_concept<point> { | |
typedef point_concept type; | |
}; | |
template<> | |
struct point_traits<point> { | |
typedef ld coordinate_type; | |
static inline coordinate_type get(const point& point, orientation_2d orient) { | |
return (orient == HORIZONTAL) ? point.x : point.y; | |
} | |
}; | |
} | |
} | |
using res_t = voronoi_diagram<ld>; | |
int main() { | |
cout.precision(20); | |
cout << fixed; | |
int x, y, n; | |
cin >> x >> y >> n; | |
vector<point> p(n); | |
for (int i = 0; i < n; i++) { | |
cin >> p[i].x >> p[i].y; | |
} | |
for (int i = 0; i < n; i++) { | |
p.push_back({-p[i].x, p[i].y}); | |
p.push_back({p[i].x, -p[i].y}); | |
p.push_back({2 * x - p[i].x, p[i].y}); | |
p.push_back({p[i].x, 2 * y - p[i].y}); | |
} | |
res_t vd; | |
construct_voronoi(p.begin(), p.end(), &vd); | |
res_t::const_cell_iterator it = vd.cells().begin(); | |
vector<vector<point>> points(n); | |
for (int i = 0; it != vd.cells().end(); i++, it++) { | |
const auto& cell = *it; | |
const auto* edge = cell.incident_edge(); | |
int j = cell.source_index(); | |
if (j >= n) | |
continue; | |
do { | |
points[j].emplace_back( | |
edge->vertex0()->x(), | |
edge->vertex0()->y() | |
); | |
edge = edge->next(); | |
} while (edge != cell.incident_edge()); | |
} | |
for (int i = 0; i < n; i++) { | |
auto mn = min_element(points[i].begin(), points[i].end(), [](const point& a, const point& b) -> bool { | |
if (fabsl(a.x - b.x) > 1e-8) | |
return a.x < b.x; | |
else | |
return a.y < b.y; | |
}); | |
rotate(points[i].begin(), mn, points[i].end()); | |
cout << points[i].size() << endl; | |
for (const point& q : points[i]) | |
cout << q.x << " " << q.y << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Маленький визуалайзер.
Принимает на вход путь до теста, путь до ответа и путь до места, куда сохранить картинку.