Triangles

题意

给定平面上的 N 个点。

从中选择三个点组成三角形，要求有一条边平行于 x 轴，另一条边平行于 y 轴。

输出最大三角形面积的两倍。

思路

暴力枚举

最直接的做法是枚举三个点，再判断它们是否能组成坐标轴对齐的直角三角形：

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/**
 * 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 14:11
 * update_at: 2026-07-11 14:13
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int x[MAXN], y[MAXN]; // 第 i 个柱子的坐标

long long calc_with_corner(int c, int a, int b) {
    long long best = 0;

    if (y[c] == y[a] && x[c] == x[b]) {
        best = llabs(x[a] - x[c]) * llabs(y[b] - y[c]);
    }

    if (y[c] == y[b] && x[c] == x[a]) {
        long long value = llabs(x[b] - x[c]) * llabs(y[a] - y[c]);
        if (best < value) {
            best = value;
        }
    }

    return best;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    long long ans = 0;

    // 枚举无序三点，再检查三个点中谁可以作为直角顶点。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                long long value = calc_with_corner(i, j, k);
                if (ans < value) {
                    ans = value;
                }

                value = calc_with_corner(j, i, k);
                if (ans < value) {
                    ans = value;
                }

                value = calc_with_corner(k, i, j);
                if (ans < value) {
                    ans = value;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

本题 $N \leqslant 100$ ，三重循环大约是 $10^6$ 次，可以直接通过。

按角色枚举

正式代码可以把三点的角色固定下来：

i 是直角顶点；
j 和 i 有相同的 y 坐标，提供水平边；
k 和 i 有相同的 x 坐标，提供竖直边。

如果这两个条件成立，那么两倍面积就是：

text

1abs(x[j] - x[i]) * abs(y[k] - y[i])

题目要求输出的正是两倍面积，所以不需要再除以 2。

代码

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

const int MAXN = 105;

int n;
int x[MAXN], y[MAXN]; // 第 i 个柱子的坐标

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    long long ans = 0;

    // 枚举 i 为直角顶点，j 提供水平边，k 提供竖直边。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j || y[i] != y[j]) {
                continue;
            }

            for (int k = 1; k <= n; k++) {
                if (i == k || x[i] != x[k]) {
                    continue;
                }

                long long base = llabs(x[j] - x[i]);
                long long height = llabs(y[k] - y[i]);
                long long area2 = base * height;
                if (ans < area2) {
                    ans = area2;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

三层循环枚举三个点，时间复杂度为 $O(N^3)$ 。

只保存坐标数组，空间复杂度为 $O(N)$ 。

总结

这题不需要复杂几何。

关键是把合法三角形看成“一个直角顶点 + 一个同 y 的点 + 一个同 x 的点”，然后直接用底乘高得到两倍面积。

目录

题意

思路

暴力枚举

按角色枚举

代码

复杂度

总结