NSOqwq

题解 CF1466A 【Bovine Dilemma】

题目大意

在一个平面直角坐标系内,$X$ 轴上有 $n$ 个点(这些点的 $Y$ 坐标均为 $0$)。还有一个点在坐标系 $x: 0, \ y: 1$ 的位置上。用这个点与那 $n$ 个点中的任意两点构成一个三角形,求出构成的所有三角形中不同面积的个数。

简化版题意

三角形的面积公式为 $\dfrac{a\cdot h}2$,其中 $a$ 为一边的长度,$h$ 为这条边上的高的长度。

很显然这题里每个三角形的 $h$ 都为 $1$。

所以求出有多少种不同的底边长 $a$ 即可。

即,每次在 $n$ 个点中选出 $2$ 个点,计算它们的距离(此题中它们都在 $X$ 轴上,只用计算出它们的 $X$ 坐标差的绝对值即可)。答案为不同的距离的个数。

实现方法

$O(n^2)$ 暴力 $+$ STL 的 set 去重。

代码

#include <cstdio>
#include <set>
#include <iostream>
using std::set;
int a;
int k[10001];
int main() {
    scanf("%d", &a);
    while (a--) { // 多组数据
        int n;
        set<int> s;
        scanf("%d", &n);
        for (int i = 1; i <= n; i += 1) {
            scanf("%d", &k[i]); // 输入
        }
        for (int i = 1; i <= n - 1; i += 1) {
            for (int j = i + 1; j <= n; j += 1) {
                s.insert(k[j] - k[i]); // set去重
            }
        }
        int cnt = 0;
        for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
            ++cnt;
        }
        printf("%d\n", cnt); // 输出
    }
    return 0;
}

2021-01-01 18:51:06 in 题解