UVa 270

From Algorithmist
Jump to navigation Jump to search

270 - Lining Up[edit]

Summary[edit]

Given n distinct points in two-dimensional plane, find the maximum number of points which lie in an arbitrary line. An is described below. A naive algorithm will simply time out since n can be as big as 700.

Explanation[edit]

  • The initial step to solve this problem is by sorting the points based on their y-coordinates in ascending order. In case of ties, sort the points based on their x-coordinates in ascending order.
  • The next step is to give each point a turn to become a pivot point. In each turn, create a new set based on the remaining points (the ones which have greater indices than the pivot point index) and sort these points angularly with respect to the pivot point. Using the fact that this new set is sorted angularly, a simple algorithm can be devised to find the maximum number of points on a line whose bottom-left endpoint is the pivot.
  • One may ask why the points whose indices are less than pivot point are omitted during each pivot turn. Those points can be safely ignored without worrying the final result won't be optimal. When an earlier point is a part of the optimal line, then the optimal result should have already been computed in an earlier pivot turn (remember the fact that the points were initially sorted based on their Cartesian coordinates).

Gotcha's[edit]

  • If you encountered lots of RTEs, most likely you didn't parse the input file correctly.

Input[edit]

5

0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

1 0
2 0
3 0
4 0 
5 0
6 0

1 1
2 2
3 3
4 4
5 5
6 6
7 7

1 1
2 2
3 3
4 4
1 2
2 3
3 4
4 5

1 -1
2 -2
3 -3
4 -4
1 -2
2 -3
3 -4
4 -5

Output[edit]

8

6

7

4

4

Solutions[edit]