powerssquare rootoverflowP0129

Sprinkler reach

A garden has one sprinkler and n flower pots. The first line gives the sprinkler position x0, y0 and the radius r its water reaches. The second line gives the number of pots n, and each of the next n lines gives a pot position x, y. A pot gets water if the (straight-line) distance between the sprinkler and the pot is at most r. On the first line print how many pots get water. On the second line print the smallest integer that is at least r and, used as the radius, makes every pot get water (the radius is never reduced). So if every pot already gets water, print r as it is.

Input: every coordinate is an integer from -100000 to 100000, 0 ≤ r ≤ 300000, 1 ≤ n ≤ 1000
Output: two lines: the number of watered pots, the smallest integer radius needed that is at least r

Example 1 · stdin

stdout

2
7

main.py Programming language Runtime version

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

The distance is √(dx² + dy²), but comparing the squares dx² + dy² <= r² keeps everything exact with integers only.
The size of the square is the trap.
Coordinate differences go up to 200,000, so the squared distance reaches 8×10^10, beyond a 32-bit int (about 2.1 billion).
Java and C# need long, C and C++ long long; with int it silently overflows and gives a nonsense value.
Python integers have no size limit, and numbers in JS, TS and Craykon are exact integers up to 2^53, so they are fine in this range.
Powers are Python/JS/TS **, Java/C# Math.pow/Math.Pow, C pow, C++ std::pow, and the last four return a floating-point double.
Craykon has no power operator, so write dx * dx.
For a square, dx * dx is the simplest and exact.
In C, C++, Java, C#, JS, TS and Python, dx ^ 2 is bitwise XOR, not a power, so it gives a wrong value without any error.
The second line is √D rounded up, where D is the largest squared distance.
Python gets an integer square root directly with math.isqrt; elsewhere the safe habit is to estimate with sqrt, correct it by comparing s * s with D, and round up (a double square root is right in this range, but can be off by one for bigger numbers).
Square root is Python math.sqrt, JS/TS Math.sqrt, Java Math.sqrt, C# Math.Sqrt, C sqrt (<math.h>), C++ std::sqrt, Craykon Mathf.Sqrt.
Using the rounded-down square root without rounding up leaves the radius one short.

Pythonmain.py · 17 lines

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))

JavaScriptmain.js · 13 lines

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));

TypeScriptmain.ts · 14 lines

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));

JavaMain.java · 23 lines

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));    }}

C#Main.cs · 28 lines

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));    }}

C++main.cpp · 24 lines

#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';}

Cmain.c · 24 lines

#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;}

Craykonmain.cray · 34 lines

first = Console.ReadNumbers();x0 = first[0];y0 = first[1];r = first[2];n = Console.ReadLine().ToNumber();watered = 0;far = 0; // 가장 먼 화분까지 거리의 제곱for (i = 0; i < n; i++){    p = Console.ReadNumbers();    dx = p[0] - x0;    dy = p[1] - y0;    d2 = dx * dx + dy * dy; // 거듭제곱 연산자가 없으니 곱해서 제곱한다    if (d2 <= r * r)    {        watered += 1;    }    far = Mathf.Max(far, d2);}s = Mathf.Floor(Mathf.Sqrt(far));while (s * s > far){    s -= 1; // 실수 제곱근이 한 칸 어긋나도 바로잡는다}while ((s + 1) * (s + 1) <= far){    s += 1;}if (s * s < far){    s += 1; // 올림}Console.WriteLine(watered);Console.WriteLine(Mathf.Max(r, s));