Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
@vasalf

This comment has been minimized.

Copy link
Owner Author

vasalf commented Dec 18, 2019

10
100000 100000 10
95057 44624
90385 43349
99794 42611
89837 45516
95886 35311
83775 45251
85026 54175
77546 40640
88563 62328
73745 49117
@vasalf

This comment has been minimized.

Copy link
Owner Author

vasalf commented Dec 19, 2019

100 100 4
44 3
43 4
56 3
53 11
@AntonYermilov

This comment has been minimized.

Copy link

AntonYermilov commented Dec 19, 2019

12 12 12
1 6   
2 9
3 10
6 11
9 10
10 9
11 6
10 3
9 2
6 1
3 2
2 3
@AntonYermilov

This comment has been minimized.

Copy link

AntonYermilov commented Dec 19, 2019

Маленький визуалайзер.
Принимает на вход путь до теста, путь до ответа и путь до места, куда сохранить картинку.

import sys 
from pathlib import Path
import plotly.offline as py
import plotly.graph_objs as go


def main(test_in: Path, test_out: Path, test_plot: Path):
    for path in [test_in, test_out, test_plot]:
        if not path.parent.exists():
            path.parent.mkdir(parents=True)

    traces = []

    with test_in.open('r') as inp:
        w, h, n = map(int, inp.readline().split())
        points = list(map(str.split, inp.readlines()))
        xs, ys = [float(pt[0]) for pt in points], [float(pt[1]) for pt in points]
        traces.append(go.Scatter(x=xs, y=ys, mode='markers'))

    with test_out.open('r') as inp:
        for _ in range(n):
            edges_x, edges_y = [], []
            k = int(inp.readline())
            for _ in range(k):
                x, y = map(float, inp.readline().split())
                edges_x.append(x)
                edges_y.append(y)
            edges_x.append(edges_x[0])
            edges_y.append(edges_y[0])
            traces.append(go.Scatter(x=edges_x, y=edges_y, mode='lines'))

    C = max(w, h)
    w = w * 1000 // C
    h = h * 1000 // C
    layout = go.Layout(width=w, height=h, showlegend=False)
    figure = go.Figure(data=traces, layout=layout)
    py.plot(figure, filename=str(test_plot))


if __name__ == '__main__':
    test_id = sys.argv[1]
    main(Path('tests', f'{test_id}.in'), Path('tests', f'{test_id}.out'), Path('plots', f'{test_id}.html'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.