Farm

Time limit1sMemory limit1024 MB

Summary

Find a longest route of trees Mr. P can visit by driving straight left, right, up, or diagonally up, and the fewest road rollers that cover the non-horizontal ruts.

Level: Hard9 of 10
Topics: Graph, Sorting, Greedy
Solved: No attempts yet

Statement

The farm can be treated as a two-dimensional Euclidean plane. There are $n$ trees, numbered $1, 2, \dots, n$ . Each tree is a point on the plane, and tree $i$ has coordinates $(x_i, y_i)$ . All tree coordinates are pairwise distinct.

Mr. P starts at the origin $(0,0)$ and drives. In each round, he chooses one of five directions: left, right, up, 45 degrees upper left, or 45 degrees upper right. A direction can be chosen only if driving that way reaches a tree he has never visited. He drives straight in the chosen direction and stops at the nearest unvisited tree in that direction. If no direction is available, he stops. Mr. P follows an optimal route, meaning one that visits the most trees. If several optimal routes exist, he may choose any of them.

Mr. S found that Mr. P's car leaves a rut on the farm. A rut is a line segment between two trees, or between the origin and a tree. Mr. S considers ruts in directions other than left and right (up, 45 degrees upper left, and 45 degrees upper right) unsightly. He will rent road rollers to reinforce the areas that might have such ruts. Formally, these areas are the segments contained in at least one optimal route.

A road roller works as follows:

It starts at the origin or at any tree.
It may move up, 45 degrees upper left, or 45 degrees upper right. It may stop or change direction only at a tree.
It may pass only through areas that might have non-horizontal ruts. An area may be passed by several road rollers.

Mr. P and Mr. S ask two questions: (1) find an optimal route for Mr. P, and (2) find the minimum number of road rollers needed.

Input

The first line contains an integer $n$ , the number of trees. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ , separated by a single space, the coordinates of the $i$ -th tree.

Output

The output has three lines. The first line is $m$ , the maximum number of trees Mr. P may visit. The second line contains the $m$ trees Mr. P visits, separated by single spaces. The third line is the minimum number of road rollers required.

Constraints

Test Case	$n$	Coordinate Range	Additional Constraints
1	$n=5$	$\\|x_i\\| \le 100$ , $0 < y_i \le 100$
2	$n=10$
3	$n=100$	$\\|x_i\\| \le 10\,000$ , $0 < y_i \le 10\,000$
4	$n=1000$
5	$n=5000$	$\\|x_i\\| \le 1\,000\,000$ , $0 < y_i \le 1\,000\,000$	The optimal route is unique.
6
7	$n=50\,000$
8	$n=5000$	$\\|x_i\\| \le 1\,000\,000$ , $0 < y_i \le 1\,000\,000$	All $y_i$ are unique.
9	$n=50\,000$
10
11	$n=5000$	$\\|x_i\\| \le 1\,000\,000$ , $0 < y_i \le 1\,000\,000$	For any integer $Y$ , at most $1000$ trees satisfy $y_i = Y$ . Additionally, there exists an optimal solution such that the road rollers won't pass through the same place twice.
12
13	$n=50\,000$
14
15	$n=10\,000$	$\\|x_i\\| \le 1\,000\,000\,000$ , $0 < y_i \le 1\,000\,000\,000$	For any integer $Y$ , at most $1000$ trees satisfy $y_i = Y$ .
16
17	$n=30\,000$
18
19	$n=50\,000$
20

Examples2

Example 1
Input
```
6
-1 1
1 1
-2 2
0 8
0 9
0 10
```
Expected output
```
3
2 1 3
3
```
Example 2
Input
```
4
0 1
-2 1
2 1
3 2
```
Expected output
```
4
1 2 3 4
2
```