정원에 스프링클러 하나와 화분 n개가 있다. 첫 줄에 스프링클러의 위치 x0, y0과 물이 닿는 반지름 r이 주어진다. 둘째 줄에 화분 수 n이 주어지고, 다음 n줄에 화분의 위치 x, y가 하나씩 주어진다. 스프링클러와 화분 사이의 거리(직선 거리)가 r 이하이면 그 화분은 물을 맞는다. 첫째 줄에 물을 맞는 화분의 수를 출력하라. 둘째 줄에, r 이상의 정수 가운데 반지름으로 쓰면 모든 화분이 물을 맞는 가장 작은 수를 출력하라(반지름은 줄이지 않는다). 그래서 이미 모든 화분이 물을 맞으면 r을 그대로 출력한다.
0 0 5 4 3 4 6 0 -1 -1 0 -7
2 7
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
거리는 √(dx² + dy²)이지만, 제곱한 채로 dx² + dy² <= r²를 비교하면 정수만으로 정확해요.
제곱의 크기가 함정이에요.
좌표 차가 20만까지라 거리의 제곱은 8×10^10까지 커져서 32비트 int(약 21억)를 넘어요.
Java·C#은 long, C·C++은 long long으로 계산해야 하고, int로 하면 조용히 넘쳐서 엉뚱한 값이 나와요.
Python의 정수는 크기 제한이 없고, JS·TS·크레이콘의 수는 2^53까지 정수가 정확해서 이 범위에서는 괜찮아요.
거듭제곱은 Python·JS·TS **, Java·C# Math.pow/Math.Pow, C pow, C++ std::pow이고, 뒤의 넷은 실수(double)를 돌려줘요.
크레이콘에는 거듭제곱 연산자가 없어서 dx * dx로 써요.
제곱은 dx * dx가 가장 단순하고 정확해요.
C·C++·Java·C#·JS·TS·Python에서 dx ^ 2는 거듭제곱이 아니라 비트 XOR이라, 오류 없이 틀린 값이 나와요.
둘째 줄은 가장 먼 거리의 제곱 D에 대해 √D를 올림한 값이에요.
Python은 math.isqrt로 정수 제곱근을 바로 얻고, 다른 언어는 sqrt로 어림한 뒤 s * s와 D를 비교해 바로잡고 올림하는 습관이 안전해요(이 범위에서는 double 제곱근이 맞지만, 더 큰 수에서는 한 칸 어긋날 수 있어요).
제곱근은 Python math.sqrt, JS·TS Math.sqrt, Java Math.sqrt, C# Math.Sqrt, C sqrt(<math.h>), C++ std::sqrt, 크레이콘 수학.제곱근이에요.
내림 제곱근을 올림하지 않고 쓰면 반지름이 1 모자라요.
import math x0, y0, r = map(int, input().split())n = int(input())watered = 0far = 0 # 가장 먼 화분까지 거리의 제곱for _ in range(n): x, y = map(int, input().split()) d2 = (x - x0) ** 2 + (y - y0) ** 2 # 제곱끼리 비교하면 정수만으로 정확하다 if d2 <= r ** 2: watered += 1 far = max(far, d2)s = math.isqrt(far) # 정수 제곱근(내림)if s * s < far: s += 1 # 올림print(watered)print(max(r, s))const [x0, y0, r, n, ...pts] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let watered = 0;let far = 0; // 가장 먼 화분까지 거리의 제곱for (let i = 0; i < n; i++) { const d2 = (pts[2 * i] - x0) ** 2 + (pts[2 * i + 1] - y0) ** 2; // 8×10^10 이하라 number로 정확하다 if (d2 <= r ** 2) watered++; far = Math.max(far, d2);}let s = Math.floor(Math.sqrt(far));while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다while ((s + 1) * (s + 1) <= far) s++;if (s * s < far) s++; // 올림console.log(watered + "\n" + Math.max(r, s));import { readFileSync } from "node:fs";const [x0, y0, r, n, ...pts]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let watered = 0;let far = 0; // 가장 먼 화분까지 거리의 제곱for (let i = 0; i < n; i++) { const d2: number = (pts[2 * i] - x0) ** 2 + (pts[2 * i + 1] - y0) ** 2; // 8×10^10 이하라 number로 정확하다 if (d2 <= r ** 2) watered++; far = Math.max(far, d2);}let s: number = Math.floor(Math.sqrt(far));while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다while ((s + 1) * (s + 1) <= far) s++;if (s * s < far) s++; // 올림console.log(watered + "\n" + Math.max(r, s));import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x0 = sc.nextLong(), y0 = sc.nextLong(), r = sc.nextLong(); int n = sc.nextInt(); int watered = 0; long far = 0; // 가장 먼 화분까지 거리의 제곱 for (int i = 0; i < n; i++) { long dx = sc.nextLong() - x0, dy = sc.nextLong() - y0; long d2 = dx * dx + dy * dy; // long이라야 넘치지 않는다(최대 8×10^10) if (d2 <= r * r) watered++; far = Math.max(far, d2); } long s = (long) Math.sqrt(far); while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다 while ((s + 1) * (s + 1) <= far) s++; if (s * s < far) s++; // 올림 System.out.println(watered); System.out.println(Math.max(r, s)); }}using System;using System.Linq; class Program{ static void Main() { long[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); long x0 = first[0], y0 = first[1], r = first[2]; int n = int.Parse(Console.ReadLine()); int watered = 0; long far = 0; // 가장 먼 화분까지 거리의 제곱 for (int i = 0; i < n; i++) { long[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); long dx = p[0] - x0, dy = p[1] - y0; long d2 = dx * dx + dy * dy; // long이라야 넘치지 않는다(최대 8×10^10) if (d2 <= r * r) watered++; far = Math.Max(far, d2); } long s = (long)Math.Sqrt(far); while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다 while ((s + 1) * (s + 1) <= far) s++; if (s * s < far) s++; // 올림 Console.WriteLine(watered); Console.WriteLine(Math.Max(r, s)); }}#include <algorithm>#include <cmath>#include <iostream> int main() { long long x0, y0, r; int n; std::cin >> x0 >> y0 >> r >> n; int watered = 0; long long far = 0; // 가장 먼 화분까지 거리의 제곱 for (int i = 0; i < n; i++) { long long x, y; std::cin >> x >> y; long long dx = x - x0, dy = y - y0; long long d2 = dx * dx + dy * dy; // long long이라야 넘치지 않는다(최대 8×10^10) if (d2 <= r * r) watered++; far = std::max(far, d2); } long long s = static_cast<long long>(std::sqrt(static_cast<double>(far))); while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다 while ((s + 1) * (s + 1) <= far) s++; if (s * s < far) s++; // 올림 std::cout << watered << '\n' << std::max(r, s) << '\n';}#include <math.h>#include <stdio.h> int main(void) { long long x0, y0, r; int n; scanf("%lld %lld %lld %d", &x0, &y0, &r, &n); int watered = 0; long long far = 0; // 가장 먼 화분까지 거리의 제곱 for (int i = 0; i < n; i++) { long long x, y; scanf("%lld %lld", &x, &y); long long dx = x - x0, dy = y - y0; long long d2 = dx * dx + dy * dy; // long long이라야 넘치지 않는다(최대 8×10^10) if (d2 <= r * r) watered++; if (d2 > far) far = d2; } long long s = (long long)sqrt((double)far); while (s * s > far) s--; // 실수 제곱근이 한 칸 어긋나도 바로잡는다 while ((s + 1) * (s + 1) <= far) s++; if (s * s < far) s++; // 올림 printf("%d\n%lld\n", watered, s > r ? s : r); return 0;}first = 콘솔.수들읽기();x0 = first[0];y0 = first[1];r = first[2];n = 콘솔.줄읽기().수로변환();watered = 0;far = 0; // 가장 먼 화분까지 거리의 제곱반복 (i = 0; i < n; i++){ p = 콘솔.수들읽기(); dx = p[0] - x0; dy = p[1] - y0; d2 = dx * dx + dy * dy; // 거듭제곱 연산자가 없으니 곱해서 제곱한다 만약 (d2 <= r * r) { watered += 1; } far = 수학.큰수(far, d2);}s = 수학.내림(수학.제곱근(far));동안 (s * s > far){ s -= 1; // 실수 제곱근이 한 칸 어긋나도 바로잡는다}동안 ((s + 1) * (s + 1) <= far){ s += 1;}만약 (s * s < far){ s += 1; // 올림}콘솔.쓰기(watered);콘솔.쓰기(수학.큰수(r, s));