Space Boomerang
Time limit3sMemory limit128 MB
Given M direction vectors in N-dimensional space, find every vector that cannot appear with a nonzero coefficient in any linear combination summing to zero.
- Level
Hard8 of 10
- Topics
- Math, Geometry, Implementation
- Solved
- No attempts yet
Problem
Far outside of our universe, the children of hyperspace creatures play the following game. They have a "boomerang" toy that they can program and then throw. Naturally, they want it to come back to the same place.
To program the toy, they have a set of modules that they can install into it. Each module pushes the toy along one fixed direction. For every module they install, they enter a non-zero distance that the toy will travel along that module's direction (they do not have to install every module in a single game). A distance may be positive or negative; a negative distance means the toy travels in the opposite direction.
After programming, they throw the boomerang. It moves through space using all installed modules simultaneously, until they all run out of power. The toy returns to its starting point exactly when the vector sum of (distance direction) over the installed modules is zero. The children play many rounds, and modules may be reused between rounds.
They want to have as much fun as possible by using many different modules. However, some modules may be useless: it is impossible to install such a module (with a non-zero distance) together with any choice of the other modules and still make the boomerang return to its starting point. Help the children find every such useless module.
Input
The first line contains two integers and separated by a space (, ), where is the number of modules and is the number of dimensions of the hyperspace.
Each of the next lines contains real numbers separated by spaces, giving the coordinates of one module's direction in -dimensional space. The modules are numbered through in the order they appear in the input. Each coordinate has at most two digits after the decimal point, and its absolute value is at most .
Output
On the first line, print one integer : the number of useless modules.
On each of the next lines, print the index of one useless module, in the same order as they appear in the input (that is, in increasing index order). If there are no useless modules, print only a line containing .