Codeforces 851C

发表于 |

题目

给$N$个不重合的$5$维空间的点。点$p$为好点，当且仅当不存在$2$个其他的不同的点$a,b$，使得角$apb$小于$90$度。夹角用类似$2$维的点乘定义。问哪些点是好点。

数据范围

$1\le N \le 10^3 \quad |坐标| \le 10^3$

做法

$5$维不好考虑，先从$2$维考虑。$2$维平面上，一个点固定了，最多有4个点和他能不成锐角，再多一个点就一定会有$2$个点和他成锐角。$3$维时，最多$6$个点。推广到$5$维，最多有$10$个点。所以，当$N>11$时，答案一定是$0$，其他情况直接$N^3$暴力算。

直接三重循环暴力算也是可以的。因为当顶点和某条边上的点固定了，第$3$重循环最多循环$9$次。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e3 + 5;
const double eps = 1e-7;
const double PI = acos(-1.0);
int sgn(double x)
{
  if (x > eps) return 1;
  else if (x < -eps) return -1;
  return 0;
}
template<class T>
struct Point
{
  T x[5];
  Point () {}
  Point (int v1, int v2, int v3, int v4, int v5)
  {
    x[0] = v1;
    x[1] = v2;
    x[2] = v3;
    x[3] = v4;
    x[4] = v5;
  }
  Point operator - (const Point b) const
  {
    return Point(x[0] - b.x[0], x[1] - b.x[1], x[2] - b.x[2], x[3] - b.x[3], x[4] - b.x[4]);
  }
  T operator * (const Point &b) const
  {
    T tmp = 0;
    for (int i = 0; i < 5; ++i) tmp += x[i] * b.x[i];
    return tmp;
  }
};
Point<double> p[MAX_N];
int N;
int ans[MAX_N], ansSize;
bool check(const Point<double> &o, const Point<double> &a, const Point<double> &b)
{
  Point<double> oa = a - o;
  Point<double> ob = b - o;
  double tmp = (oa * ob) / sqrt(oa * oa) / sqrt(ob * ob);
  tmp = acos(tmp);
  return sgn(tmp - PI / 2.0) >= 0;
}
int main()
{
  cin >> N;
  if (N > 11) {puts("0"); return 0;}
  for (int i = 0; i < N; ++i) {
    double x[5];
    for (int j = 0; j < 5; ++j) {
      scanf("%lf", &x[j]);
    }
    p[i] = Point<double>(x[0], x[1], x[2], x[3], x[4]);
  }
  for (int i = 0; i < N; ++i) {
    bool flag = true;
    for (int j = 0; flag && j < N; ++j) {
      if (j == i) continue;
      for (int k = j + 1; flag && k < N; ++k) {
        if (k == i) continue;
        if (!check(p[i], p[j], p[k])) {
          flag = false;
        }
      }
    }
    if (flag) ans[ansSize++] = i + 1;
  }
  printf("%d\n", ansSize);
  for (int i = 0; i < ansSize; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

总结

过的人多了，有可能直接暴力就行。