把笔直的步道看作数轴，数轴上每个整数位置都放着一块标志石。 步道旁边立着 n 盏路灯。 对每盏路灯，给出步道上离这盏路灯最近的点的位置 x、路灯到步道的距离 d 和灯光能照到的距离 r。 位置 p 的标志石与这盏路灯之间的距离是 (p - x)² + d² 的平方根。 如果这个距离不超过 r，这块标志石就被这盏路灯照亮。 对每盏路灯，求出被它照亮的标志石中最小的位置和最大的位置。 另外，对每盏路灯数出被这一盏灯照亮的标志石数，求出其中最大的值。
输入
第一行给出路灯的数量 n(1 ≤ n ≤ 1,000)。 接下来 n 行每行给出一盏路灯的整数 x、d、r，用一个空格隔开。 -1,000,000,000 ≤ x ≤ 1,000,000,000，0 ≤ d ≤ 30,000,000，1 ≤ r ≤ 30,000,000。
输出
在前 n 行，按给出的顺序对每盏路灯输出被它照亮的标志石的最小位置和最大位置，用一个空格隔开。 如果被照亮的标志石只有一块，把它的位置输出两次。 如果没有被照亮的标志石，这一行只输出一个 -。 在最后一行输出一盏路灯照亮的标志石数中最大的值。 如果没有任何路灯能照到标志石，最后一行输出 0。 数不带逗号输出。
样例 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
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
求出 r² - d² 的平方根向下取整的值 s，被照亮的标志石就是从 x - s 到 x + s。 求这个平方根的方法，以及传入负数时发生的事，各语言并不相同。 Python 的 math.isqrt() 只用整数运算求整数平方根。 传入负数会因 ValueError 而停止，math.sqrt() 对负数也是 ValueError。 JavaScript 和 TypeScript 的 Math.sqrt()、Java 的 Math.sqrt()、C# 的 Math.Sqrt()、C 和 C++ 的 sqrt()、Craykon 的 数学.平方根() 都是浮点平方根，传入负数时不报错而返回 NaN。 浮点平方根向下取整变成整数之后，再用整数确认一次 s * s 没有超过、(s + 1) * (s + 1) 超过了，就不必担心误差。 陷阱一：负数的平方根。 示例 1 的第三盏路灯 d = 6、r = 5，所以 r² - d² 是 -11，灯光照不到步道。 如果不先把这种情况分出来，Python 会因 ValueError 而停止。 陷阱二：把 NaN 转成整数。 在 Java 中 (long) Math.sqrt(-11) 不报错就变成 0。 于是第三行输出的不是 - 而是 -7 -7。 在 C 和 C++ 中把 NaN 转成整数是未定义行为。 陷阱三：原样输出的 NaN。 JavaScript 在第三行输出 NaN NaN，而且 NaN 混进 Math.max，最后一行也变成 NaN。 陷阱四：平方的溢出。 示例 1 的第五盏路灯 r = 100,000，所以 r² 是 10,000,000,000，超出了 32 位整数。 在 C# 中用 int 求平方，不报错就变成别的数，输出的不是 -80000 80000 而是 -45880 45880。 Java、C、C++ 也必须用 64 位整数求平方。 JavaScript 和 Craykon 的数在 9,007,199,254,740,992 以内是精确的，所以能原样存下本题的平方(最大 900,000,000,000,000)。 陷阱五：刚好照到的路灯。 第二盏路灯 d = r = 5，所以 r² - d² 是 0，正前方的一块标志石(位置 10)被照亮。 如果把 0 及以下都当作照不到，输出的就不是 10 10 而是 -。 陷阱六：四舍五入。 第四盏路灯的 r² - d² 是 3，平方根约为 1.73。 向下取整是 1，所以答案是 1 3；四舍五入则变成 2，输出 0 4。
Pythonmain.py · 18 行
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
가로등수 = 控制台.读行().转数字();최대 = 0;循环 (i = 0; i < 가로등수; i++){ 칸들 = 控制台.读行().去空白().分割(); 위치 = 칸들[0].转数字(); 떨어진거리 = 칸들[1].转数字(); 닿는거리 = 칸들[2].转数字(); 남은 = 닿는거리 * 닿는거리 - 떨어진거리 * 떨어진거리; // (p - x)²이 넘지 않아야 하는 값 如果 (남은 < 0) { // 수학.제곱근(음수)는 오류 없이 NaN이다: 먼저 가른다 控制台.输出("-"); 继续; } 반 = 数学.向下取整(数学.平方根(남은)); 当 (반 * 반 > 남은) { 반--; // 실수 제곱근의 오차에 대비한 정수 확인 } 当 ((반 + 1) * (반 + 1) <= 남은) { 반++; } 控制台.输出(위치 - 반 + " " + (위치 + 반)); 최대 = 数学.较大值(최대, 2 * 반 + 1);}控制台.输出(최대);