欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #432 (Div. 2) - C - Five Dimensional Points

程序员文章站 2022-07-15 16:08:43
...

C. Five Dimensional Points

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 Codeforces Round #432 (Div. 2) - C - Five Dimensional Points and Codeforces Round #432 (Div. 2) - C - Five Dimensional Pointsis acute (i.e. strictly less than Codeforces Round #432 (Div. 2) - C - Five Dimensional Points). Otherwise, the point is called good.

The angle between vectors Codeforces Round #432 (Div. 2) - C - Five Dimensional Points and Codeforces Round #432 (Div. 2) - C - Five Dimensional Points in 5-dimensional space is defined as Codeforces Round #432 (Div. 2) - C - Five Dimensional Points, where Codeforces Round #432 (Div. 2) - C - Five Dimensional Points is the scalar product and Codeforces Round #432 (Div. 2) - C - Five Dimensional Points is length of Codeforces Round #432 (Div. 2) - C - Five Dimensional Points.

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 Codeforces Round #432 (Div. 2) - C - Five Dimensional Points 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:

Codeforces Round #432 (Div. 2) - C - Five Dimensional Points

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

 

题意:

有n个五维的点,求有多少个“好“点,对于“好”点、“坏”点的定义如下:

“好”点:设该点为a,在所给点中任意两个不相等且不为a的点b,c,向量ab与向量bc的夹角均不为锐角。

“坏”点:不是“好”点的点都是“坏”点

思路:

可以从二维三维的方向来考虑,在二维中,一个“好”点的周围最多有4个点(x正负方向两个,y正负方向两个),三维则有6个(加上z方向上两个),可以知道,五维的情况下,一个“好”点周围最多有10个点,加上自身,即图中有“好”点的情况下,最多有11个点,即n>11时不可能存在“好”点,然后n<=11的情况就枚举一下就行了。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int point[1010][10],n,cnt = 0,ans[20],dis[20][10],flag;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) for(int j=1;j<=5;j++) scanf("%d",&point[i][j]);
    if(n>11) {printf("0\n"); return 0;}
    for(int i=1;i<=n;i++)
    {
        memset(dis,0,sizeof dis);
        flag = 1;
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            for(int k=1;k<=5;k++) dis[j][k] = point[j][k] - point[i][k];//向量 ij
            for(int k=1;k<j;k++)
            {
                if(k==i) continue;
                int sum = 0;//向量ij与向量ik的向量点乘
                for(int l=1;l<=5;l++) sum+=dis[k][l]*dis[j][l];
                if(sum<=0) continue;//夹角>=90
                else {flag = 0; break;}
            }
            if(!flag) break;
        }
        if(flag) ans[++cnt] = i;
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
    return 0;
}