Five Dimensional Points CodeForces

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 $\text{[math]}$ and $\text{[math]}$ is acute (i.e. strictly less than $\text{[math]}$ ). Otherwise, the point is called good.

The angle between vectors $\text{[math]}$ and $\text{[math]}$ in 5-dimensional space is defined as $\text{[math]}$ , where $\text{[math]}$ is the scalar product and $\text{[math]}$ is length of $\text{[math]}$ .

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

Copy

output

Copy

1
1

input

Copy

output

Copy

Note

In the first sample, the first point forms exactly a $\text{[math]}$ 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:

$\text{[math]}$

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

题意：

给你n个五维空间上的n个点。

让你求出“好”的点的数量。

“好”的点的定义是：

对于一个点i，不存在任何其他两个点，j,k，（三个点互不相同）使得向量 i->j和向量 i - > k 是锐角。

思路：

判断两个向量的夹角是否是锐角可以通过向量的点积来判断。

五维空间的点积和二维三维的都一样，都是对应坐标相乘再相加。

然后每一次点积后的结果都可以得出这样的结论。

如图，如果点积后的结果小于等于零，那么证明∠J I K不是锐角。

那么就得出结论 j 和k都不是good点，因为对于j，有i和k是的所成的角是锐角。

k同理。

而如果点积结果大于0，那么证明角jik是锐角，所以i不是good point

需要一个数组vis来维护哪些点是已经被确定不是good点的，以此来降低时间复杂度。

注意到枚举的时候，第三个变量k，设为j+1开始枚举，这样不会让i，j，k每一次重复计算而导致答案错误。

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d
",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int vis[maxn];
struct node
{
    ll a,b,c,d,e;
}arr[maxn];
int n;
ll f(int i,int j,int k)
{
    ll a1=arr[j].a-arr[i].a;
    ll a2=arr[k].a-arr[i].a;
    ll b1=arr[j].b-arr[i].b;
    ll b2=arr[k].b-arr[i].b;
    ll c1=arr[j].c-arr[i].c;
    ll c2=arr[k].c-arr[i].c;
    ll d1=arr[j].d-arr[i].d;
    ll d2=arr[k].d-arr[i].d;
    ll e1=arr[j].e-arr[i].e;
    ll e2=arr[k].e-arr[i].e;
    ll res=a1*a2+b1*b2+c1*c2+d1*d2+e1*e2;
    return res;
}
int main()
{
    //freopen("D:\common_text\code_stream\in.txt","r",stdin);
    //freopen("D:\common_text\code_stream\out.txt","w",stdout);

    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>arr[i].a>>arr[i].b>>arr[i].c>>arr[i].d>>arr[i].e;
    }
    repd(i,1,n)
    {
        if(i==2)
        {
            i=2;
        }
        if(vis[i])
            continue;
        repd(j,1,n)
        {
            if(i==j)
            {
                continue;
            }
            repd(k,j+1,n)
            {
                if(k==j||k==i)
                {
                    continue;
                }
                if(f(i,j,k)<=0)
                {
                    vis[j]=vis[k]=1;
                    break;
                }else
                {
                    vis[i]=1;
                    break;
                }
            }
            if(vis[i])
                break;
        }
    }
    int ans=0;
    repd(i,1,n)
    {
        if(!vis[i])
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    repd(i,1,n)
    {
        if(!vis[i])
        {
            cout<<i<<" ";
        }
    }cout<<endl;
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

本博客为本人原创，如需转载，请必须声明博客的源地址。本人博客地址为：www.cnblogs.com/qieqiemin/ 希望所写的文章对您有帮助。