usaco-3.4.1 闭合的栅栏

形式化题目

给定平面上 $N$ 个互不重合的顶点 $v_0, v_1, \dots, v_{N-1}$ （按逆时针顺序）以及相邻顶点连成的 $N$ 条闭合栅栏（线段 $v_i v_{i+1}$ ，下标取模 $N$ ），和一个观察者坐标 $(x, y)$ 。

判断这 $N$ 条线段是否构成一个合法的闭合栅栏：任意两条栅栏除公共顶点外不得有其他交点（不允许自交、不允许相邻栅栏共线重叠）。不合法时输出 NOFENCE。
若合法，找出所有能被观察者看到的栅栏：存在一条从 $(x, y)$ 发出的射线，其第一个穿过的栅栏就是它。与目光平行（观察者与该栅栏共线）的栅栏不计入可见。
每条可见栅栏用两端点输出，顶点按输入顺序（序号小的在前）书写；所有栅栏按"最后一个点"的输入序号排序，序号相同时按"第一个点"的序号排序，第一行输出可见栅栏数。

数据范围： $3 < N < 200$ ，顶点坐标绝对值不超过 $1000$ ，观察者坐标为 16 位整数。

正解

思路

朴素做法。 在每条栅栏 $AB$ 上撒一批采样点，对每个采样点 $P$ 检查线段 $obs \to P$ 是否与其他栅栏相交，只要有一个点不被挡住就算可见。问题是采样点再多也只是近似：漏掉的细小可见区间会导致误判，无法保证正确性。

瓶颈在哪里。 对固定的栅栏 $AB$ 和固定的另一条栅栏 $CD$ ，" $obs \to P$ 被 $CD$ 挡住"这件事随着 $P$ 在 $AB$ 上移动只会在两种位置发生改变：

视线恰好擦过 $CD$ 的端点，即 $P$ 位于直线 $obs \to C$ 或 $obs \to D$ 与 $AB$ 的交点上；
$P$ 恰好越过线段 $CD$ 本身。由于栅栏合法（简单多边形、顶点互不重合），非相邻栅栏不相交，相邻栅栏只交于公共顶点——而公共顶点的视线分界已经被上一条覆盖。

所以遮挡状态的全部分界点就是"观察者到各顶点的视线与 $AB$ 的交点"。

优化后的做法。 用这 $O(N)$ 条视线把 $AB$ 分成 $O(N)$ 个开段，段内每一个点的可见性完全相同，于是每段取一个中点测试即可——有限个候选点从"近似"变成"完备"。中点用 Fraction 精确表示，所有跨立判定化成整数叉积，不引入浮点误差。

单个候选点 $P$ 是否被栅栏 $CD$ 挡住，用严格跨立判据： $obs、P$ 在直线 $CD$ 两侧且 $C、D$ 在直线 $obsP$ 两侧，即视线严格穿过 $CD$ 的内部（擦过顶点不算穿过）。

flowchart LR
    A["读入 N / 观察者 / 顶点"] --> B{"任意两栅栏<br/>有多余交点?"}
    B -- 是 --> C["NOFENCE"]
    B -- 否 --> D["对每条栅栏 AB:<br/>obs→各顶点视线切分 AB"]
    D --> E["每段取中点 P:<br/>整数叉积跨立判定"]
    E -- 存在不被挡的中点 --> F["该栅栏可见"]
    E -- 全段被挡 --> G["该栅栏不可见"]
    F --> H["按 (max,min) 下标排序输出"]
    G --> H

输出排序。 边 $i$ 连接顶点 $i$ 与 $(i+1) \bmod N$ ，"最后一个点"即两者中输入序号大者。排序关键字取 $(\max(i, i+1), \min(i, i+1))$ ；末尾闭合边 $N-1 \to 0$ 的关键字是 $(N-1, 0)$ ，正好排在 $(N-1, N-2)$ 之前，与样例一致。

样例对照（观察者 $(5,5)$ ，样例输出 7 条）： $(0,0)-(7,0)$ 、 $(5,2)-(7,5)$ 等外侧栅栏直接可见； $(7,0)-(5,2)$ 、 $(3,5)-(4,9)$ 等则被更近的栅栏整段遮挡，所有分段中点都被挡住，因此不可见。

代码

Python 版：

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 06:55
# update_at: 2026-10-01 06:55

import sys
from fractions import Fraction

Point = tuple[int, int]


def cross(o: Point, a: Point, b: Point) -> int:
    """oa × ob：>0 左转，<0 右转，=0 三点共线。"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def on_segment(p: Point, a: Point, b: Point) -> bool:
    """已知三点共线时，p 是否落在 ab 线段上（含端点）。"""
    return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
            and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))


def touches(p1: Point, p2: Point, q1: Point, q2: Point) -> bool:
    """两条线段是否有公共点：严格跨立，或端点落在对方线段上（含共线重叠）。"""
    d1, d2 = cross(p1, p2, q1), cross(p1, p2, q2)
    d3, d4 = cross(q1, q2, p1), cross(q1, q2, p2)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True
    return (d1 == 0 and on_segment(q1, p1, p2)
            or d2 == 0 and on_segment(q2, p1, p2)
            or d3 == 0 and on_segment(p1, q1, q2)
            or d4 == 0 and on_segment(p2, q1, q2))


def is_simple(pts: list[Point]) -> bool:
    """合法闭合栅栏：任意两条栅栏除公共顶点外没有别的交点（不自交、不重叠）。"""
    n = len(pts)
    for i in range(n):
        a1, a2 = pts[i], pts[(i + 1) % n]
        for j in range(i + 1, n):
            b1, b2 = pts[j], pts[(j + 1) % n]
            adjacent = j == i + 1 or (i == 0 and j == n - 1)
            if not adjacent:
                if touches(a1, a2, b1, b2):
                    return False
                continue
            # 相邻栅栏天然交于公共顶点；只有当两者共线且在该顶点之外还互相覆盖才不合法
            shared, pa, pb = (a2, a1, b2) if j == i + 1 else (a1, a2, b1)
            if cross(shared, pa, pb) == 0 and (
                    on_segment(pb, shared, pa) or on_segment(pa, shared, pb)):
                return False
    return True


def visible(i: int, pts: list[Point], obs: Point) -> bool:
    """栅栏 i（pts[i]→pts[i+1]）是否可被观察者看到：段上存在一个不被遮挡的点。"""
    n = len(pts)
    a1, a2 = pts[i], pts[(i + 1) % n]
    ox, oy = obs
    if cross(a1, a2, obs) == 0:
        return False  # 观察者与栅栏共线，目光沿栅栏方向，按题意不算可见
    ux, uy = a2[0] - a1[0], a2[1] - a1[1]

    # obs→各顶点的直线把 AB 分成若干开段，段内"被谁挡住"不变，只需测每段中点
    cuts = {Fraction(0), Fraction(1)}
    for cx, cy in pts:
        ex, ey = cx - ox, cy - oy
        den = ex * uy - ey * ux  # 交点参数分母 cross(e, U)，=0 即与 AB 平行
        if den == 0:
            continue
        num = ey * (a1[0] - ox) - ex * (a1[1] - oy)  # 参数分子 -cross(e, A-obs)
        if den < 0:
            num, den = -num, -den
        if 0 < num < den:  # 交点确实落在线段 AB 内部
            cuts.add(Fraction(num, den))

    # 其余栅栏的跨立判据预计算：相对观察者的位移、方向 c、观察者所在侧
    others = []
    for k in range(n):
        if k == i:
            continue
        q1, q2 = pts[k], pts[(k + 1) % n]
        cx, cy = q2[0] - q1[0], q2[1] - q1[1]
        side = cx * (oy - q1[1]) - cy * (ox - q1[0])  # cross(c, obs-q1)
        others.append((q1[0] - ox, q1[1] - oy,
                       q2[0] - ox, q2[1] - oy, cx, cy, side))

    seq = sorted(cuts)
    for lo, hi in zip(seq, seq[1:]):
        mid = (lo + hi) / 2
        den = mid.denominator
        # 中点方向向量 (P-obs)·den：P = A + mid·U，全程整数避免浮点误差
        vx = (a1[0] - ox) * den + mid.numerator * ux
        vy = (a1[1] - oy) * den + mid.numerator * uy
        blocked = False
        for r1x, r1y, r2x, r2y, cx, cy, side in others:
            t1 = vx * r1y - vy * r1x          # cross(P-obs, q1-obs)
            t2 = vx * r2y - vy * r2x          # cross(P-obs, q2-obs)
            if t1 == 0 or t2 == 0 or (t1 ^ t2) >= 0:
                continue                      # 观察者两端不在对方直线两侧，非跨立
            # cross(c, P-q1) 的符号 = cross(c, P-obs) + den·side 的符号
            u = cx * vy - cy * vx + den * side
            if side != 0 and u != 0 and (side ^ u) < 0:
                blocked = True                # 视线严格穿过该栅栏，被它挡住
                break
        if not blocked:
            return True
    return False


def solve() -> None:
    lines = sys.stdin.read().splitlines()
    n = int(lines[0])
    head = lines[1].split()
    obs = (int(head[0]), int(head[1]))

    # 顶点逐行读取：一行给出 (x, y)；若该行只有一个数，则与下一行首数合成一个顶点
    pts: list[Point] = []
    row = 2
    while len(pts) < n:
        toks = lines[row].split()
        if len(toks) > 1:
            pts.append((int(toks[0]), int(toks[1])))
            row += 1
        else:
            pts.append((int(toks[0]), int(lines[row + 1].split()[0])))
            row += 2

    if not is_simple(pts):
        print("NOFENCE")
        return

    seen = [i for i in range(n) if visible(i, pts, obs)]
    # 按"最后一个点"（输入序号大者）排序，相同时再按"第一个点"排序
    seen.sort(key=lambda i: (max(i, (i + 1) % n), min(i, (i + 1) % n)))

    out = [str(len(seen))]
    for i in seen:
        j = (i + 1) % n
        first, last = (pts[i], pts[j]) if i < j else (pts[j], pts[i])
        out.append(f"{first[0]} {first[1]} {last[0]} {last[1]}")
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:12
 * update_at: 2026-10-06 10:12
 */
// 闭合栅栏：先判简单多边形，再对每条栅栏用"观察者视线切分 + 段中点跨立"判定可见性
#include <bits/stdc++.h>
typedef long long ll;

const int MAXN = 205;

ll px[MAXN], py[MAXN]; // px[i], py[i]：第 i 个顶点坐标（下标 0..n-1）
ll n, ox, oy;          // n：顶点数，(ox, oy)：观察者位置
ll sn[MAXN], sx[MAXN], sy[MAXN], sc[MAXN]; // 待输出栅栏的端点序号与坐标

// oa × ob：>0 左转，<0 右转，=0 三点共线
ll cross(ll oax, ll oay, ll bax, ll bay) {
    return oax * bay - oay * bax;
}

// 最大公约数：把分数约到最简，避免中间量溢出 long long
ll gcd_ll(ll a, ll b) {
    while (b != 0) { ll t = a % b; a = b; b = t; }
    return a < 0 ? -a : a;
}

// 已知三点共线时，q 是否落在线段 ab 上（含端点）
bool on_seg(ll qx, ll qy, ll ax, ll ay, ll bx, ll by) {
    return std::min(ax, bx) <= qx && qx <= std::max(ax, bx)
        && std::min(ay, by) <= qy && qy <= std::max(ay, by);
}

// 两条线段是否有公共点：严格跨立，或端点落在对方线段上（含共线重叠）
bool touches(ll p1x, ll p1y, ll p2x, ll p2y,
             ll q1x, ll q1y, ll q2x, ll q2y) {
    ll d1 = cross(p2x - p1x, p2y - p1y, q1x - p1x, q1y - p1y);
    ll d2 = cross(p2x - p1x, p2y - p1y, q2x - p1x, q2y - p1y);
    ll d3 = cross(q2x - q1x, q2y - q1y, p1x - q1x, p1y - q1y);
    ll d4 = cross(q2x - q1x, q2y - q1y, p2x - q1x, p2y - q1y);
    if (d1 * d2 < 0 && d3 * d4 < 0) return true;
    return (d1 == 0 && on_seg(q1x, q1y, p1x, p1y, p2x, p2y))
        || (d2 == 0 && on_seg(q2x, q2y, p1x, p1y, p2x, p2y))
        || (d3 == 0 && on_seg(p1x, p1y, q1x, q1y, q2x, q2y))
        || (d4 == 0 && on_seg(p2x, p2y, q1x, q1y, q2x, q2y));
}

// 相邻栅栏 i、k 是否"共线且在公共顶点之外还互相覆盖"（这种情况不合法）
bool adjacent_overlap(ll i, ll k) {
    if (k == i + 1) {           // 顺序相邻：公共顶点是 i+1，两边的另一端是 i 和 k+1
        ll shared = i + 1;
        ll pa = i, pb = (k + 1) % n;
        ll cx = cross(px[pa] - px[shared], py[pa] - py[shared],
                      px[pb] - px[shared], py[pb] - py[shared]);
        if (cx != 0) return false;
        return on_seg(px[pb], py[pb], px[shared], py[shared], px[pa], py[pa])
            || on_seg(px[pa], py[pa], px[shared], py[shared], px[pb], py[pb]);
    }
    // 闭合相邻（i=0, k=n-1）：公共顶点是 0，两边的另一端是 1 和 k
    ll shared = 0;
    ll pa = 1, pb = k;
    ll cx = cross(px[pa] - px[shared], py[pa] - py[shared],
                  px[pb] - px[shared], py[pb] - py[shared]);
    if (cx != 0) return false;
    return on_seg(px[pb], py[pb], px[shared], py[shared], px[pa], py[pa])
        || on_seg(px[pa], py[pa], px[shared], py[shared], px[pb], py[pb]);
}

// 检查 n 条栅栏是否构成合法闭合栅栏：任意两条除公共顶点外无其他交点
bool is_simple() {
    for (ll i = 0; i < n; i++) {
        ll j = (i + 1) % n;
        for (ll k = i + 1; k < n; k++) {
            ll l = (k + 1) % n;
            bool adjacent = (k == i + 1) || (i == 0 && k == n - 1);
            if (!adjacent) {
                if (touches(px[i], py[i], px[j], py[j],
                            px[k], py[k], px[l], py[l])) return false;
            } else {
                // 相邻栅栏天然交于公共顶点，只额外检查是否共线重叠
                if (adjacent_overlap(i, k)) return false; // k 是相邻边的编号
            }
        }
    }
    return true;
}

// 栅栏 i（顶点 i → (i+1)%n）是否可被观察者看到：段上存在一个不被遮挡的点
bool visible(ll i) {
    ll j = (i + 1) % n;
    ll ax = px[i], ay = py[i], bx = px[j], by = py[j];
    if (cross(bx - ax, by - ay, ox - ax, oy - ay) == 0) return false;
    ll ux = bx - ax, uy = by - ay; // 栅栏方向向量

    // 分段断点：参数 t ∈ [0,1]，0/1 是端点，其余是观察者到各顶点的视线与 AB 的交点
    ll cut_t[2 * MAXN], cut_a[MAXN], cut_b[MAXN]; // 交点表示成 num/den，数对存下
    ll m = 0;
    cut_t[m++] = 0; cut_a[m - 1] = 0; cut_b[m - 1] = 1;
    cut_t[m++] = 1; cut_a[m - 1] = 1; cut_b[m - 1] = 1;
    for (ll k = 0; k < n; k++) {
        ll ex = px[k] - ox, ey = py[k] - oy;
        ll den = ex * uy - ey * ux;               // 交点参数分母，=0 即视线与 AB 平行
        if (den == 0) continue;
        ll num = ey * (ax - ox) - ex * (ay - oy); // 分子 -cross(e, A-obs)
        if (den < 0) { num = -num; den = -den; }
        if (num > 0 && num < den) {               // 交点确实落在线段 AB 内部
            ll g = gcd_ll(num, den);              // 约分，防止后续放大时溢出
            cut_t[m] = num / g; cut_a[m] = num / g; cut_b[m] = den / g;
            m++;
        }
    }
    // 按 t 值（分数）从小到大排序断点：冒泡即可，m ≤ 2n
    for (ll p = 0; p < m - 1; p++)
        for (ll q = 0; q + 1 < m - p; q++)
            if (cut_a[q] * cut_b[q + 1] > cut_a[q + 1] * cut_b[q]) {
                std::swap(cut_t[q], cut_t[q + 1]);
                std::swap(cut_a[q], cut_a[q + 1]);
                std::swap(cut_b[q], cut_b[q + 1]);
            }

    // 其余栅栏的跨立判据预计算：相对观察者的端点位移、方向 c、观察者所在侧
    ll r1x[MAXN], r1y[MAXN], r2x[MAXN], r2y[MAXN], ccx[MAXN], ccy[MAXN], cside[MAXN];
    ll cnt = 0;
    for (ll k = 0; k < n; k++) {
        if (k == i) continue;
        ll q1x = px[k], q1y = py[k], q2x = px[(k + 1) % n], q2y = py[(k + 1) % n];
        r1x[cnt] = q1x - ox; r1y[cnt] = q1y - oy;
        r2x[cnt] = q2x - ox; r2y[cnt] = q2y - oy;
        ccx[cnt] = q2x - q1x; ccy[cnt] = q2y - q1y;
        cside[cnt] = ccx[cnt] * (oy - q1y) - ccy[cnt] * (ox - q1x); // cross(c, obs-q1)
        cnt++;
    }

    // 相邻开段取中点测试：段内每一点可见性完全相同
    for (ll p = 0; p + 1 < m; p++) {
        // 中点分数 (p1n + p2n)/(2·b1·b2)：等价于 (lo+hi)/2 化成同一分母
        ll p1n = cut_a[p] * cut_b[p + 1], p2n = cut_a[p + 1] * cut_b[p];
        ll dden = 2 * cut_b[p] * cut_b[p + 1];
        ll g = gcd_ll(p1n + p2n, dden);           // 中点同样约分
        ll mn = (p1n + p2n) / g, md = dden / g;
        // 中点方向向量 (P-obs)·md：P = A + t·U，全程整数运算不丢精度
        ll vx = (ax - ox) * md + mn * ux;
        ll vy = (ay - oy) * md + mn * uy;
        bool blocked = false;
        for (ll k = 0; k < cnt; k++) {
            ll t1 = vx * r1y[k] - vy * r1x[k]; // cross(P-obs, q1-obs)
            ll t2 = vx * r2y[k] - vy * r2x[k]; // cross(P-obs, q2-obs)
            if (t1 == 0 || t2 == 0) continue;  // 擦过端点不算穿过
            if ((t1 < 0) == (t2 < 0)) continue; // 观察者方向两端不在对方直线两侧
            // cross(c, P-q1) 的符号 = cross(c, P-obs) + md·side 的符号
            ll u = ccx[k] * vy - ccy[k] * vx + md * cside[k];
            if (cside[k] != 0 && u != 0 && (cside[k] < 0) != (u < 0)) {
                blocked = true; // 视线严格穿过该栅栏，被它挡住
                break;
            }
        }
        if (!blocked) return true; // 存在不被遮挡的中点，栅栏可见
    }
    return false;
}

int main() {
    std::cin >> n >> ox >> oy;
    for (ll i = 0; i < n; i++) std::cin >> px[i] >> py[i];

    if (!is_simple()) {
        std::cout << "NOFENCE" << std::endl;
        return 0;
    }

    // 收集所有可见栅栏：边 i 连接顶点 i 与 (i+1)%n
    ll total = 0;
    for (ll i = 0; i < n; i++) {
        if (!visible(i)) continue;
        ll j = (i + 1) % n;
        ll first, last; // "最后一个点"= 输入序号大者
        if (i < j) { first = i; last = j; }
        else       { first = j; last = i; }
        sn[total] = first; sx[total] = px[first]; sy[total] = py[first];
        sc[total] = last;  // 只再存 last 的下标，坐标输出时再取
        total++;
    }
    // 按"最后一个点"的输入序号排序，相同时按"第一个点"排序
    for (ll p = 0; p < total - 1; p++)
        for (ll q = 0; q + 1 < total - p; q++) {
            bool need = sc[q] > sc[q + 1]
                || (sc[q] == sc[q + 1] && sn[q] > sn[q + 1]);
            if (need) {
                std::swap(sn[q], sn[q + 1]);
                std::swap(sx[q], sx[q + 1]);
                std::swap(sy[q], sy[q + 1]);
                std::swap(sc[q], sc[q + 1]);
            }
        }
    std::cout << total << "\n";
    for (ll k = 0; k < total; k++) {
        std::cout << sx[k] << " " << sy[k] << " "
                  << px[sc[k]] << " " << py[sc[k]] << "\n";
    }
    return 0;
}

复杂度

合法性检查：两两枚举栅栏对， $O(N^2)$ 。
可见性判定：每条栅栏切出 $O(N)$ 段，段中点对 $O(N)$ 条其余栅栏做跨立试验；找得到可见中点会立即退出，最坏（整条被挡）为 $O(N^3)$ ， $N < 200$ 时约 $8 \times 10^6$ 次叉积。
空间 $O(N)$ 。本仓库 11 组真实数据实测单组不超过 0.1s、内存约 16MB。

总结

合法性用线段两两求交在 $O(N^2)$ 内完成；可见性的核心观察是"遮挡状态只在观察者到顶点的视线处分界"，它把无限的连续采样压缩成每条栅栏 $O(N)$ 个精确候选点，配合整数叉积跨立判定得到与标准解同阶的最坏 $O(N^3)$ 算法，且无浮点误差。

usaco-3.4.1 闭合的栅栏

目录

形式化题目

正解

思路

代码

复杂度

总结