Codeforces Round #432 (Div. 2) - C - Five Dimensional Points
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 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.
题意:
有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;
}
推荐阅读
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Codeforces 851C - Five Dimensional Points - 数学 暴力
-
Codeforces Round #432 (Div. 2) - C - Five Dimensional Points
-
Codeforces Round #658 (Div. 2)C1. Prefix Flip (Easy Version)(贪心)
-
Codeforces Round #658 (Div. 2) (C1、C2)
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #659 (Div. 2) C、String Transformation 1(思维+set)
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Codeforces Round #651 (Div. 2) C. Number Game