blog/hill-climbing-shortlist

Cosmin Negruseri
23 iunie 2015

1. You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the sum of square distances from the points in A to P is minimum.
2. You are given a list of A of n points with integer coordinates in the 3d plane. Find another point P(x, y) such that the maximum of the Manhattan distances from the points in A to P is minimum. (the manhattan distance between (x1, y1, z1) and (x2, y2, z2) is |x1 - x2| + |y1 - y2| + |z1 - z2|)
3. You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the sum of distances from the points in A to P is minimum.
4. You are given a convex polygon P with n vertices, find out the radius of the largest inscribed circle in that polygon..
5. You are given a list A of n points in the plane, find out the minimum enclosing circle.
6. Given a number n, find out a placement of n queens on an nxn chessboard so that they don’t attack each other.
   Given n and S integers, find out a permutation p such that 1 x p¹ + 2 x p² + .. + n x p[n] = S.
7. 2n knights have to sit around a roundtable. Each knight is friends with n + 1 other knights. Find a seating arrangement such that each knight is placed between two friends.
8. Given two line segments in 3d space find the minimum distance between them.
9. A party of n people is too large and has to be split to two tables. Given that each of the people has exactly three friends, find out a seating arrangement such that each person sits at a table where at least two other of his friends are seated.
10. Given a set A of n black points and a set B of n white points (no three points are collinear), join each point in A with one point in B respectively such that no two segments will intersect.
11. Given a set A with n points and a set B with m points, find a line that separates the two sets.
12. Given two points A and B and a circle C, find a point D on C such that AD + DB is minimized.
13. Given a rectangle R find a list L of n points in it such that the sum of distances between all pairs of points in L is maximized.