Think of a straight walking path as a number line, with one marker stone at every integer position.
There are n streetlamps beside the path.
For each lamp you are given the position x of the point on the path closest to the lamp, the distance d from the lamp to the path, and the distance r its light reaches.
The distance between the marker stone at position p and this lamp is the square root of (p - x)² + d².
If this distance is r or less, that stone is lit by this lamp.
For each lamp, find the smallest position and the largest position among the stones lit by that lamp.
Also count, for each lamp, the stones lit by that one lamp, and find the largest of these counts.
Input
The first line contains the number of lamps n (1 ≤ n ≤ 1,000).
Each of the next n lines contains the integers x, d and r of one lamp, separated by single spaces.
-1,000,000,000 ≤ x ≤ 1,000,000,000, 0 ≤ d ≤ 30,000,000, and 1 ≤ r ≤ 30,000,000.
Output
On the first n lines, for each lamp in the given order, print the smallest position and the largest position of the stones lit by that lamp, separated by a single space.
If only one stone is lit, print its position twice.
If no stone is lit, print a single - on that line.
On the last line, print the largest number of stones lit by one lamp.
If no lamp lights any stone, print 0 on the last line.
Print numbers without commas.
Example 1 · stdin
5
0 3 5
10 5 5
-7 6 5
2 1 2
0 60000 100000
stdout
-4 4
10 10
-
1 3
-80000 80000
160001
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Once you have s, the square root of r² - d² rounded down, the lit stones run from x - s to x + s. Languages differ in how you get this square root and in what happens when you pass a negative number.
In Python, math.isqrt() finds the integer square root using only integer arithmetic. A negative argument stops with a ValueError, and math.sqrt() also raises ValueError for a negative number.
Math.sqrt() in JavaScript, TypeScript and Java, Math.Sqrt() in C#, sqrt() in C and C++, and Craykon's Mathf.Sqrt() are floating-point square roots, and for a negative number they return NaN without any error.
After rounding a floating-point square root down to an integer, checking once more with integers that s * s does not exceed the value and that (s + 1) * (s + 1) does removes any worry about error.
Trap one: the square root of a negative number. The third lamp of example 1 has d = 6 and r = 5, so r² - d² is -11 and its light does not reach the path. Without separating this case first, Python stops with a ValueError.
Trap two: turning NaN into an integer. In Java, (long) Math.sqrt(-11) becomes 0 without any error. So the third line shows -7 -7 instead of -. In C and C++, converting NaN to an integer is undefined behavior.
Trap three: NaN printed as it is. JavaScript prints NaN NaN on the third line, and since NaN gets into Math.max, the last line becomes NaN too.
Trap four: overflow of the square. The fifth lamp of example 1 has r = 100,000, so r² is 10,000,000,000, beyond a 32-bit integer. Squaring with int in C# gives a different number without any error, and the line shows -45880 45880 instead of -80000 80000. Java, C and C++ must also square with 64-bit integers. Numbers in JavaScript and Craykon are exact up to 9,007,199,254,740,992, so they hold the squares of this problem (at most 900,000,000,000,000) as they are.
Trap five: a lamp that just reaches. The second lamp has d = r = 5, so r² - d² is 0 and the one stone right in front (position 10) is lit. Treating 0 or less as dark prints - instead of 10 10.
Trap six: rounding. For the fourth lamp, r² - d² is 3 and its square root is about 1.73. Rounded down it is 1, so the answer is 1 3; rounded to nearest it becomes 2 and the line shows 0 4.
Pythonmain.py · 18 lines
import sysfrom math import isqrtlines = sys.stdin.read().split("\n")n = int(lines[0])out = []best = 0for i in range(1, n + 1): x, d, r = map(int, lines[i].split()) rest = r * r - d * d # (p - x)²이 넘지 않아야 하는 값 if rest < 0: # 음수의 제곱근은 구할 수 없다: 먼저 가른다 out.append("-") continue s = isqrt(rest) # 정수 제곱근(내림) out.append(f"{x - s} {x + s}") best = max(best, 2 * s + 1)out.append(str(best))print("\n".join(out))
JavaScriptmain.js · 20 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const out = [];let best = 0;for (let i = 1; i <= n; i++) { const [x, d, r] = lines[i].trim().split(" ").map(Number); const rest = r * r - d * d; // (p - x)²이 넘지 않아야 하는 값 if (rest < 0) { // Math.sqrt(음수)는 오류 없이 NaN이다: 먼저 가른다 out.push("-"); continue; } let s = Math.floor(Math.sqrt(rest)); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; out.push(`${x - s} ${x + s}`); best = Math.max(best, 2 * s + 1);}out.push(String(best));console.log(out.join("\n"));
TypeScriptmain.ts · 22 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const out: string[] = [];let best: number = 0;for (let i = 1; i <= n; i++) { const [x, d, r]: number[] = lines[i].trim().split(" ").map(Number); const rest: number = r * r - d * d; // (p - x)²이 넘지 않아야 하는 값 if (rest < 0) { // Math.sqrt(음수)는 오류 없이 NaN이다: 먼저 가른다 out.push("-"); continue; } let s: number = Math.floor(Math.sqrt(rest)); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; out.push(`${x - s} ${x + s}`); best = Math.max(best, 2 * s + 1);}out.push(String(best));console.log(out.join("\n"));
JavaMain.java · 31 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); long best = 0; for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split(" "); long x = Long.parseLong(parts[0]); long d = Long.parseLong(parts[1]); long r = Long.parseLong(parts[2]); long rest = r * r - d * d; // long으로 제곱해야 넘치지 않는다 if (rest < 0) { // Math.sqrt(음수)는 NaN이고 (long) NaN은 0이다: 먼저 가른다 sb.append("-\n"); continue; } long s = (long) Math.sqrt((double) rest); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; sb.append(x - s).append(' ').append(x + s).append('\n'); best = Math.max(best, 2 * s + 1); } sb.append(best).append('\n'); System.out.print(sb); }}
C#Main.cs · 33 lines
using System;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); StringBuilder sb = new StringBuilder(); long best = 0; for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); long x = long.Parse(parts[0]); long d = long.Parse(parts[1]); long r = long.Parse(parts[2]); long rest = r * r - d * d; // long으로 제곱해야 넘치지 않는다 if (rest < 0) { // Math.Sqrt(음수)는 NaN이다: 먼저 가른다 sb.Append("-\n"); continue; } long s = (long)Math.Sqrt((double)rest); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; sb.Append(x - s).Append(' ').Append(x + s).Append('\n'); best = Math.Max(best, 2 * s + 1); } sb.Append(best).Append('\n'); Console.Write(sb); }}
C++main.cpp · 29 lines
#include <algorithm>#include <cmath>#include <iostream>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; long long best = 0; for (int i = 0; i < n; i++) { long long x, d, r; cin >> x >> d >> r; long long rest = r * r - d * d; // long long으로 제곱해야 넘치지 않는다 if (rest < 0) { // sqrt(음수)는 NaN이고, NaN을 정수로 바꾸는 것은 정해지지 않은 동작이다 cout << "-\n"; continue; } long long s = static_cast<long long>(sqrt(static_cast<double>(rest))); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; cout << x - s << ' ' << x + s << '\n'; best = max(best, 2 * s + 1); } cout << best << '\n'; return 0;}
Cmain.c · 25 lines
#include <math.h>#include <stdio.h>int main(void) { int n; if (scanf("%d", &n) != 1) return 1; long long best = 0; for (int i = 0; i < n; i++) { long long x, d, r; if (scanf("%lld %lld %lld", &x, &d, &r) != 3) return 1; long long rest = r * r - d * d; /* long long으로 제곱해야 넘치지 않는다 */ if (rest < 0) { /* sqrt(음수)는 NaN이고, NaN을 정수로 바꾸는 것은 정해지지 않은 동작이다 */ printf("-\n"); continue; } long long s = (long long)sqrt((double)rest); while (s * s > rest) s--; /* 실수 제곱근의 오차에 대비한 정수 확인 */ while ((s + 1) * (s + 1) <= rest) s++; printf("%lld %lld\n", x - s, x + s); if (2 * s + 1 > best) best = 2 * s + 1; } printf("%lld\n", best); return 0;}
Craykonmain.cray · 28 lines
가로등수 = Console.ReadLine().ToNumber();최대 = 0;for (i = 0; i < 가로등수; i++){ 칸들 = Console.ReadLine().Trim().Split(); 위치 = 칸들[0].ToNumber(); 떨어진거리 = 칸들[1].ToNumber(); 닿는거리 = 칸들[2].ToNumber(); 남은 = 닿는거리 * 닿는거리 - 떨어진거리 * 떨어진거리; // (p - x)²이 넘지 않아야 하는 값 if (남은 < 0) { // 수학.제곱근(음수)는 오류 없이 NaN이다: 먼저 가른다 Console.WriteLine("-"); continue; } 반 = Mathf.Floor(Mathf.Sqrt(남은)); while (반 * 반 > 남은) { 반--; // 실수 제곱근의 오차에 대비한 정수 확인 } while ((반 + 1) * (반 + 1) <= 남은) { 반++; } Console.WriteLine(위치 - 반 + " " + (위치 + 반)); 최대 = Mathf.Max(최대, 2 * 반 + 1);}Console.WriteLine(최대);