Nice Lines

시간 제한0.2초메모리 제한1024 MB

요약

주어진 N개 직선까지의 유클리드 거리 합을 최소로 하는 점을, 그 합을 계산하는 장치를 적게 써서 찾는 문제.

난이도: 보통10점 중 6점
유형: 기하, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Roxette the pirate princess has arrived to the secret island in the Remeian archipelago. There, a famous treasure, the golden nice lines is rumoured to be buried.

The secret island is a square, $2 × 10^{12}$ by $2 × 10^{12}$ meters long and tall. Any point on the island is described using Cartesian coordinates, with $(0, 0)$ being at the center, and the two axes being parallel to its sides.

There are $N$ golden nice lines buried on the island. The $i$ th one for $0 ≤ i < N$ occupies the set of all real-valued points $(x, y)$ described by the linear equation $y = a\_ix + b\_i$ .

Roxette can use a special device, called a lineometer. Given any point $p$ on the island, the lineometer will compute the sum of the distances1 from point $p$ to each of the $N$ golden nice lines.

Unfortunately, the lineometer has a limited number of uses. Can you help Roxette find the treasure with a small enough number of lineometer uses?

1The Euclidean distance between a point and a line is the length of the shortest line segment that touches both the line and the point.

제한

$1 ≤ N ≤ 100$
$−10\\,000 ≤ a\_i , b\_i ≤ 10\\,000$
No two lines are parallel.

예제1

예제 1

입력

solve(
/* subtask id = */ 1,
/* N =          */ 1)

예상 출력

query(0, 0) returns 0
query(1, 1) returns 0
the lines are(
/* a = */ {1},
/* b = */ {0})