codeforce 850A Five Dimensional Points(特殊判别)

72 阅读 0 评论 48 点赞

我是靠谱客的博主结实香烟，最近开发中收集的这篇文章主要介绍codeforce 850A Five Dimensional Points(特殊判别)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送

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个点，然你求有多少个好点分别是什么.
好点：任意两个不同于这个点的点，如果其与改点相连后的夹角大于等于90
坏点：存在小于90的

对于二维空间，对于任意一个点其上下左右四个方向只能最多各有一个点，因为如果再多一个点，则与其相连后夹角必定小于90，所以大于5个点时就不存在好点。同理三维空间大于7个点时就不存在好点，同理类比五维空间就是大于11个点时不存在好点。利用这条结论，在小于11时可以暴力。

代码如下：

#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<set>

using namespace std;
const int MAX_N = 1010;
struct point{
    int a,b,c,d,e;
    void setpoint(){
        cin >> a >> b >> c >> d >> e;
    }
};
double eps = 0;
point rng[MAX_N];
int n;
int mul(point A,point B){//求两向量相乘
    return A.a*B.a + A.b*B.b + A.c*B.c + A.d*B.d + A.e*B.e;
}
point sub(point A,point B){//A-B相当于求向量BA
    point c;
    c.a = A.a - B.a;
    c.b = A.b - B.b;
    c.c = A.c - B.c;
    c.d = A.d - B.d;
    c.e = A.e - B.e;
    return c;
}
void solve(){
    if(n > 11){
        cout << "0" << endl;
        return;
    }
    int ans[20],top = 0;
    for(int i=1;i<=n;i++){
        bool isok = true;
        for(int j=1;j<=n;j++){
            if(j == i)  continue;
            for(int k=1;k<=n;k++){
                if(k != j && k != i){
                    point x = sub(rng[j],rng[i]);
                    point y = sub(rng[k],rng[i]);
                    int xx = mul(x,y);
                    double yy = sqrt(mul(x,x))*sqrt(mul(y,y));
                    double cosB = xx/yy;
                    if((cosB > 0 && cosB <= 1)){
                        isok = false;
                    }
                }
            }
        }
        if(isok){
            ans[++top] = i;
        }
    }
    cout << top << endl;
    for(int i=1;i<=top;i++){
        cout << ans[i] << endl;
    }
}
int main(void){
    cin >> n;
    for(int i=1;i<=n;i++){
        rng[i].setpoint();
    }
    solve();


    return 0;
}