[POI 2011] WYK-Plot

GitHub 跳转原题关系图返回列表

二分最大误差，使用随机增量最小覆盖圆与最长可行前缀贪心构造连续分组。

OJ: luogu

题目 ID: P3517

难度:省选/NOI-

标签:二分答案计算几何最小覆盖圆随机化python

日期: 2026-07-16 18:28

题意

把点序列切成不超过 m 个连续非空段，每段用一个新点代替。最小化所有原点到所属新点的最大距离，并输出误差、段数和各段代表点。

思路

一段点能被误差 radius 代替，当且仅当它们的最小覆盖圆半径不超过 radius。

固定半径后从左到右贪心：每次取当前起点能覆盖的最长前缀。这不会比提前截断使用更多段，因为更长的第一段只会给后续留下更短的后缀。段的可行性随右端点单调，因此先指数扩展范围，再二分出最长端点。

区间最小覆盖圆使用随机增量算法。按随机顺序加入点；只有新点落在当前圆外时，才依次固定它为边界点，再固定第二、第三个边界点重建圆。最小覆盖圆最多由三个边界点确定。

外层对答案做 48 次浮点二分。最后再执行一次贪心，缓存中的最小圆圆心就是各段要输出的代表点。

Python 知识

random.Random(seed).shuffle(selected) 创建局部、可复现的随机顺序，不污染全局随机状态。
math.hypot(dx, dy) 直接计算欧氏距离，数值行为比手写开方清楚。
字典以 (left, right) 为键缓存重复区间的最小覆盖圆。
keep_segments=False 让同一个函数既能只判可行，也能在最后返回构造方案。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106import math
import random
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, group_limit = next(data), next(data)
points = [(next(data), next(data)) for _ in range(n)]
cache = {}


def diameter_circle(a, b):
    center_x = (a[0] + b[0]) / 2
    center_y = (a[1] + b[1]) / 2
    radius = math.hypot(a[0] - b[0], a[1] - b[1]) / 2
    return center_x, center_y, radius


def circumcircle(a, b, c):
    ax, ay = a
    bx, by = b
    cx, cy = c
    denominator = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
    if abs(denominator) < 1e-18:
        pairs = ((a, b), (a, c), (b, c))
        return diameter_circle(*max(pairs, key=lambda pair:
            (pair[0][0] - pair[1][0]) ** 2 + (pair[0][1] - pair[1][1]) ** 2))
    a2 = ax * ax + ay * ay
    b2 = bx * bx + by * by
    c2 = cx * cx + cy * cy
    center_x = (a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)) / denominator
    center_y = (a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)) / denominator
    return center_x, center_y, math.hypot(center_x - ax, center_y - ay)


def minimum_circle(left, right):
    key = (left, right)
    circle = cache.get(key)
    if circle is not None:
        return circle
    selected = points[left:right]
    if len(selected) == 1:
        circle = selected[0][0], selected[0][1], 0.0
    elif len(selected) == 2:
        circle = diameter_circle(*selected)
    else:
        random.Random(left * 1000003 + right).shuffle(selected)
        center_x, center_y = selected[0]
        radius = 0.0
        for i, point in enumerate(selected):
            if math.hypot(point[0] - center_x, point[1] - center_y) <= radius + 1e-9:
                continue
            center_x, center_y = point
            radius = 0.0
            for j in range(i):
                other = selected[j]
                if math.hypot(other[0] - center_x, other[1] - center_y) <= radius + 1e-9:
                    continue
                center_x, center_y, radius = diameter_circle(point, other)
                for third in selected[:j]:
                    if math.hypot(third[0] - center_x, third[1] - center_y) > radius + 1e-9:
                        center_x, center_y, radius = circumcircle(point, other, third)
        circle = center_x, center_y, radius
    if len(cache) < 250000:
        cache[key] = circle
    return circle


def partition(limit, keep_segments=False):
    segments = []
    left = 0
    while left < n:
        length = 1
        while (left + 2 * length <= n
               and minimum_circle(left, left + 2 * length)[2] <= limit + 1e-8):
            length *= 2
        low = left + length
        high = min(n, left + 2 * length)
        while low < high:
            middle = (low + high + 1) // 2
            if minimum_circle(left, middle)[2] <= limit + 1e-8:
                low = middle
            else:
                high = middle - 1
        segments.append((left, low))
        if len(segments) > group_limit:
            return None
        left = low
    return segments if keep_segments else True


low = 0.0
high = minimum_circle(0, n)[2]
for _ in range(48):
    middle = (low + high) / 2
    if partition(middle):
        high = middle
    else:
        low = middle

segments = partition(high + 1e-7, True)
print(f"{high + 1e-7:.10f}")
print(len(segments))
for left, right in segments:
    center_x, center_y, _ = minimum_circle(left, right)
    print(f"{center_x:.10f} {center_y:.10f}")

复杂度

随机增量最小覆盖圆单次期望线性。设浮点二分次数为常数 B=48，结合端点的指数查找与二分，整体期望时间可记为 $O(Bn\log n)$ ；缓存上限为 250000 个区间，空间 $O(n)$ 加缓存。

总结

本题把“最小化最大值”转成二分判定，再用连续分段的最长前缀贪心。由于是 Special Judge，样例圆心不唯一，只要输出圆心确实覆盖对应连续段即可。

P3517 [POI 2011] WYK-Plot

题目描述

We call any sequence of points in the plane a plot.

We intend to replace a given plot $(P_1,\cdots,P_n)$ with another that will have at most $m$ points ( $m\le n$ ) in such a way that it “resembles” the original plot best.

The new plot is created as follows. The sequence of points $P_1,\cdots,P_n$ can be partitioned into $s$ ( $s\le m$ ) contiguous subsequences:

$(P_{k_0+1},\cdots,P_{k_1}),(P_{k_1+1},\cdots,P_{k_2}),\cdots,(P_{k_{s-1}+1},\cdots,P_{k_s})$ where $0=k_0<k_1<k_2<\cdots<k_s=n$ ,and afterwards each subsequence $(P_{k_{i-1}+1},\cdots,P_{k_i})$ , for $i=1,\cdots,s$ ,is replaced by a new point $Q_i$ .

In that case we say that each of the points $P_{k_{i-1}+1},\cdots,P_{k_i}$ has been contracted to the point $Q_i$ .

As a result a new plot, represented by the points $Q_1,\cdots,Q_s$ , is created.

The measure of such plot’s resemblance to the original is the maximum distance of all the points $P_1,\cdots,P_n$ to the point it has been contracted to:

$max_{i=1,\cdots,s}(max_{j=k_{i-1}+1,\cdots,k_i}(d(P_j,Q_i)))$ where $d(P_j,Q_i)$ denotes the distance between $P_j$ and $Q_i$ , given by the well-known formula:

$d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

An exemplary plot $P_1,\cdots,P_7$ and the new plot $(Q_1,Q_2)$ , where $(P_1,\cdots,P_4)$ are contracted to $Q_1$ , whereas $(P_5,P_6,P_7)$ to $Q_2$ .

For a given plot consisting of $n$ points, you are to find the plot that resembles it most while having at most $m$ points, where the partitioning into contiguous subsequences is arbitrary.

Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most $0.000001$ .

输入格式

In the first line of the standard input there are two integers $n$ and $m$ , $1\le m\le n\le 100\ 000$ , separated by a single space.

Each of the following $n$ lines holds two integers, separated by a single space.

The $(i+1)$ -th line gives $x_i$ , $y_i$ , $-1\ 000\ 000\le x_i,y_i\le 1\ 000\ 000$ denoting the coordinates $(x_i,y_i)$ of the point $P_i$ .

输出格式

In the first line of the standard output one real number $d$ should be printed out, the resemblance measure of the plot found to the original one.

In the second line of the standard output there should be another integer $s$ , $1\le s\le m$ .

Next, the following $s$ lines should specify the coordinates of the points $Q_1,\cdots,Q_s$ ,one point per line.

Thus the $(i+2)$ -th line should give two real numbers $u_i$ and $v_i$ , separated by a single space, that denote the coordinates $(u_i,v_i)$ of the point $Q_i$ .All the real numbers should be printed with at most 15 digits after the decimal point.

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
43.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199

[POI 2011] WYK-Plot

目录

题意

思路

Python 知识

代码

复杂度

总结