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 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 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 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 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.