Koto 시 지하철
면접 대비시간 제한8초메모리 제한512 MB
D와 E가 주어질 때 x + y = D인 정수 점 (x, y) 중 |sqrt(x^2 + y^2) - E|를 최소로 하는 점을 찾아 그 최솟값을 출력한다.
문제
Koto 시는 아래 그림처럼 도로가 바둑판 모양으로 난 것으로 유명한 도시다. 남북으로 뻗은 도로와 동서로 뻗은 도로는 각각 1km 간격으로 놓여 있다. Koto 시의 가장 남서쪽 교차로에 있는 Koto 역을 (0, 0)으로 하고, 그곳에서 동쪽으로 x km, 북쪽으로 y km 간 위치를 (x, y)로 적는다 (0 ≤ x, y이다).
5년 뒤 열리는 올림픽으로 관광객이 늘어날 것을 내다보고, 시는 Koto 역을 기점으로 하는 새 지하철 노선을 건설하기로 했다. 지금은 Koto 역의 다음 역으로 새로 건설할 Shin-Koto 역까지 레일을 놓을 계획을 세우고 있다. 레일은 Koto 역에서 Shin-Koto 역을 향해 곧게 놓는다. 따라서 Shin-Koto 역의 위치를 (x, y)라 하면 레일의 길이는 √(x2 + y2)이다. 레일을 놓는 데 드는 비용은 놓은 레일의 길이만큼 필요하다. 레일의 길이가 1.5km처럼 소수여도 비용도 똑같이 1.5가 필요하다.
Shin-Koto 역의 위치 (x, y)는 아직 정해지지 않았고, 다음 조건을 만족하는 곳으로 정할 예정이다.
- 교차로이다. 즉,
x와y가 각각 정수이다. - Koto 역에서 도로를 따라 걸었을 때의 최단 거리가 정확히
D이다. 즉,x+y=D를 만족한다.
위 두 조건을 만족하는 곳 중에서 시가 정한 레일 예산 E와 레일 비용의 차이 | √(x2 + y2) - E | 가 최소가 되도록 Shin-Koto 역의 위치를 고른다. 여기서 |A|는 A의 절댓값을 나타낸다. 당신의 일은 위와 같이 Shin-Koto 역을 건설했을 때 레일을 놓는 데 드는 비용과 예산의 차이를 출력하는 프로그램을 작성하는 것이다.
입력
입력은 여러 데이터 세트로 구성되며, 하나의 입력에 포함되는 데이터 세트의 수는 100 이하이다. 각 데이터 세트의 형식은 다음과 같다.
D E
D (1 ≤ D ≤ 100)는 Koto 역에서 Shin-Koto 역까지 도로를 따라 걸었을 때의 최단 거리를 나타내는 정수이다. E (1 ≤ E ≤ 100)는 레일 건설을 위한 예산을 나타내는 정수이다.
입력의 끝은 공백으로 구분된 두 개의 0으로 이루어진 행으로 나타낸다.
출력
각 데이터 세트에 대해, 문제의 조건을 만족하도록 레일을 놓았을 때의 비용과 예산의 차이를 한 줄로 출력하라. 답에는 10-3을 넘는 절대 오차가 있어서는 안 된다. 각 줄의 끝에 개행을 출력하지 않거나 불필요한 문자를 출력하면 오답으로 판정되니 주의하라.
힌트
1번째 데이터 세트에서는 아래 그림처럼 Koto 역에서 도로를 따라 2km 간 교차로가 Shin-Koto 역을 건설할 위치의 후보가 된다.
각 교차로에 Shin-Koto 역을 건설했을 때 레일을 놓는 데 드는 비용과 예산 1의 차이는 다음과 같다.
- (2, 0) : | √(22 + 02) - 1 | = 1.0
- (1, 1) : | √(12 + 12) - 1 | = 0.4142135623...
- (0, 2) : | √(02 + 22) - 1 | = 1.0
따라서 비용과 예산의 차이가 최소가 되는 것은 (1, 1)에 건설했을 때이다.