Codeforces 851C - Five Dimensional Points - 数学 暴力

链接:

  http://codeforces.com/contest/851/problem/C

---

题目：

You are given set of n points in 5-dimensional space. The points are labeled from 1 to n. No two points coincide.

We will call point a bad if there are different points b and c, not equal to a, from the given set such that angle between vectors and is acute (i.e. strictly less than ). Otherwise, the point is called good.

The angle between vectors and in 5-dimensional space is defined as , where is the scalar product and is length of .

Given the list of points, print the indices of the good points in ascending order.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 103) — the number of points.

The next n lines of input contain five integers ai, bi, ci, di, ei (|ai|, |bi|, |ci|, |di|, |ei| ≤ 103) — the coordinates of the i-th point. All points are distinct.

Output

First, print a single integer k — the number of good points.

Then, print k integers, each on their own line — the indices of the good points in ascending order.

Examples

input
6
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
output
1
1
input
3
0 0 1 2 0
0 0 9 2 0
0 0 5 9 0
output
0
Note
In the first sample, the first point forms exactly a angle with all other pairs of points, so it is good.

In the second sample, along the cd plane, we can see the points look as follows:

We can see that all angles here are acute, so no points are good.

---

题意：

  给你若干个五维空间里的点，对于某个点a，如果存在两个点b和c，使得∠bac<90。，那么这个点就是一个不好的点。然后让你输出有几个好的点，然后输出所有不好的点的下标。

---

思路：

  对于每个点a，暴力枚举除了点a之外的所有点，直接根据向量的点积公式来判断ab→·ac→是否大于0，如果大于0的话说明∠bac是锐角。

---

实现：

#include <bits/stdc++.h>
using namespace std;
const int maxn = int(1e3)+7;
int node[maxn][5], ans[maxn], cnt;
bool check(int i, int j, int k) {
    int ans = 0;
    for(int x=0 ; x<5 ; x++)
        ans += (node[i][x]-node[j][x])*(node[k][x]-node[j][x]);
    return ans > 0;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n;
    scanf("%d", &n);
    for(int i=0 ; i<n ; i++) for(int j=0 ; j<5 ; j++) scanf("%d",node[i]+j);
    for(int i=0 ; i<n ; i++) {
        bool flag = true;
        for(int j=0 ; j<n && flag ; j++) {
            if(j == i) continue;
            for(int k=0 ; k<n ; k++) {
                if(k == j) continue;
                if(check(j,i,k)) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) ans[cnt++] = i+1;
    }
    printf("%d\n", cnt);
    for(int i=0 ; i<cnt ; i++) printf("%d\n", ans[i]);
    return 0;
}