Center Of Mass

3

2 votes
Dynamic Programming, Algorithms, 4D dynamic programming
Problem

You have n points with equal weights and integer coordinated on the coordinate plane. You want to select k weights and determine the center of mass of these k weights. You must select the k weights in such a way that the center of mass has an integer coordinate. 

Input format

  • First line: Two space-separated integers n and k denoting the number of points and the number of weights you want to select 
  • Next n lines: ith weight contains two integers xi and yi denoting the coordinates of the ith weight

Output format

If it is not possible to select k points that satisfies the provided condition, then print -1. Otherwise, print k integers of i indices of the selected weights.

Constraints

1n1051k201kn0xi,yi109

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

You can choose the first 3 points and their center of mass would be (4,4).

If you choose points [1,2,4] their center of mass would be (2.333,2.666), which is not an integer.

Editor Image

?