Clockwise Fence

题意

给定若干条由 $N/E/S/W$ 组成的闭合栅栏路径。路径不自交，只在最后回到起点。

判断按字符串顺序沿着栅栏走时，围住的区域在右侧还是左侧；右侧输出 CW，左侧输出 CCW。

思路

用有向面积校验

一个常见做法是按路径走出坐标点，再用多边形有向面积判断方向：

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/**
 * 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-07-11 13:35
 * update_at: 2026-07-11 13:39
 */
// brute.cpp：小数据校验解，用坐标和有向面积判断方向。
#include <bits/stdc++.h>
using namespace std;

void move_one(char ch, int &x, int &y) {
    if (ch == 'N') y++;
    if (ch == 'S') y--;
    if (ch == 'E') x++;
    if (ch == 'W') x--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int tc = 1; tc <= n; tc++) {
        string s;
        cin >> s;

        int x = 0;
        int y = 0;
        long long area2 = 0; // 多边形有向面积的 2 倍。

        for (int i = 0; i < (int)s.size(); i++) {
            int nx = x;
            int ny = y;
            move_one(s[i], nx, ny);

            area2 += 1ll * x * ny - 1ll * nx * y;

            x = nx;
            y = ny;
        }

        if (area2 > 0) {
            cout << "CCW\n";
        } else {
            cout << "CW\n";
        }
    }

    return 0;
}

在通常坐标系下，有向面积为正表示逆时针，为负表示顺时针。

累计转角

官方解析的思路是：顺时针路径整体更倾向于右转，逆时针路径整体更倾向于左转。

把方向编号为：

text

1E = 0, N = 1, W = 2, S = 3

相邻两段边形成一个转角：

左转贡献 +1；
右转贡献 -1；
直行贡献 0。

沿简单闭合曲线走一圈，如果整体是逆时针，总转角为 $+360^\circ$ ；如果整体是顺时针，总转角为 $-360^\circ$ 。

因此只需要比较每一对相邻方向：

text

1s[i] -> s[(i + 1) % len]

最后如果 total_turn > 0，输出 CCW；否则输出 CW。

以 NESW 为例：

text

1
2
3
4N -> E 右转
E -> S 右转
S -> W 右转
W -> N 右转

总转角为负，所以是 CW。

代码

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/**
 * 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-07-11 13:35
 * update_at: 2026-07-11 13:39
 */
#include <bits/stdc++.h>
using namespace std;

int direction_id(char ch) {
    if (ch == 'E') return 0;
    if (ch == 'N') return 1;
    if (ch == 'W') return 2;
    return 3; // S
}

int turn_value(char from, char to) {
    int a = direction_id(from);
    int b = direction_id(to);
    int diff = (b - a + 4) % 4;

    if (diff == 1) return 1;   // 左转 90 度。
    if (diff == 3) return -1;  // 右转 90 度。
    return 0;                  // 直行。
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int tc = 1; tc <= n; tc++) {
        string s;
        cin >> s;

        int total_turn = 0;
        int len = (int)s.size();

        for (int i = 0; i < len; i++) {
            total_turn += turn_value(s[i], s[(i + 1) % len]);
        }

        if (total_turn > 0) {
            cout << "CCW\n";
        } else {
            cout << "CW\n";
        }
    }

    return 0;
}

复杂度

每条路径扫描一遍，时间复杂度为 $O(L)$ ，其中 $L$ 是路径长度。

只使用常数个变量，额外空间复杂度为 $O(1)$ 。

总结

这题的关键是把“顺时针/逆时针”转化成局部转向的总和。

只要路径是简单闭合曲线，绕一圈后的总转角正负就能唯一确定方向。

目录

题意

思路

用有向面积校验

累计转角

代码

复杂度

总结