boost_voronoi.cpp

#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;
}

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

100 100 4
44 3
43 4
56 3
53 11

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

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

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'))