# Problem A. Farthest Point（圆周上最远整点）

## Source

### 描述

Given a circle on a two-dimentional plane.

Output the integral point in or on the boundary of the circle which has the largest distance from the center.

### 输入

One line with three floats which are all accurate to three decimal places, indicating the coordinates of the center x, y and the radius r.

For 80% of the data: |x|,|y|<=1000, 1<=r<=1000

For 100% of the data: |x|,|y|<=100000, 1<=r<=100000

### 输出

One line with two integers separated by one space, indicating the answer.

If there are multiple answers, print the one with the largest x-coordinate.

If there are still multiple answers, print the one with the largest y-coordinate.

#### 样例输入

1.000 1.000 5.000

6 1

## 题解1 - 圆周枚举

### Java

import java.io.*;
import java.util.*;
import java.util.Queue;

class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble();
Point result = solve(xd, yd, rd);
System.out.println(result.x + " " + result.y);
}

private static Point solve(double x0, double y0, double r) {
// convert double to long(accurate)
long xl0 = (long)(x0 * 1000), yl0 = (long)(y0 * 1000), rl0 = (long)(r * 1000);
Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE);
int lower_x = (int)Math.ceil(x0 - r), upper_x = (int)Math.floor(x0 + r);
for (int i = upper_x; i >= lower_x; i--) {
// circle above
long y1l = yl0 + (long)(Math.sqrt(rl0*rl0 - (i*1000 - xl0)*(i*1000 - xl0)) + 0.5);
if ((i*1000 - xl0)*(i*1000 - xl0) + (y1l - yl0)*(y1l - yl0) == rl0*rl0) {
// ensure y1 is integer
if (y1l % 1000 == 0) {
res.x = i;
res.y = y1l / 1000;
return res;
}
}
// circle below
y1l = yl0 - (long)(Math.sqrt(rl0*rl0 - (i*1000 - xl0)*(i*1000 - xl0)) + 0.5);
if ((i*1000 - xl0)*(i*1000 - xl0) + (y1l - yl0)*(y1l - yl0) == rl0*rl0) {
// ensure y1 is integer
if (y1l % 1000 == 0) {
res.x = i;
res.y = y1l / 1000;
return res;
}
}
}

return res;
}
}

## 题解2 - 整数分解

$m = 10^3(x - x_0)$, $n = 10^3(y - y_0)$, $R = 10^3r$, 那么我们有新的圆方程： $m^2 + n^2 = R^2$ 其中 m, n, R 均为整数。接下来我们看看给出的数据范围，x, y, r 均是 $10^6$ 以内，那么圆方程两边同乘 $10^6$ （括号内的数即乘上 $10^3$）后数据在 $10^{18}$ 以内。我们来估算下整数的范围，$2^{10} \approx 10^3$, Java 中 int 型为4个字节，最大为 $2^{31} - 1 \approx 2 \cdot 10^9$, long 型为8个字节，最大为 $2^{63} - 1 \approx 2^3 \cdot 10^{18}$, 估算下来应该选用 long 保存 m, n, R.

$m = \sqrt{R^2 - n^2} = \sqrt{(R + n)(R - n)}$ 由于 m 一定是整数，故根号内一定为完全平方数，由于排除了轴上的点，那么-R < n < R, 设G = gcd(R + n, R - n), $p^2 = (R + n) / G$, $q^2 = (R - n) / G$, 于是我们有m = Gpq, p > q, 由于GR + nR - n 的最大公约数，故pq一定互质，且有： $p^2 + q^2 = 2R / G$ 由于p,q 都大于等于1，那么我们能推断出G 一定是 2R 的约数！根据约数(素数)部分的基础理论，我们可以在 $O(\sqrt{2R})$ 时间内找出所有约数。然后对以上等式进行缩放得到p 的范围，枚举求解，判断p^2q^2 是否互质(最大公约数是否为1)。

### Java

import java.io.*;
import java.util.*;

class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble();
// convert double to long(accurate)
long x0 = (long)(xd * 1000), y0 = (long)(yd * 1000), r0 = (long)(rd * 1000);
Point result = solve(x0, y0, r0);
System.out.println(result.x + " " + result.y);
}

private static Point solve(long x0, long y0, long r) {
Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE);
long x_max = Long.MIN_VALUE, y_max = Long.MIN_VALUE;
// p^2 + q^2 = 2R/divisor, p > q >= 1
// 1 <= q^2 < R/G < p^2 < 2R/G ==> p >= 2
List<Long> divisors = getDivisor(r << 1);
for (long divisor : divisors) {
long lower = Math.max(2, (long)Math.sqrt(r * 1.0/ divisor));
// long upper = (long)Math.sqrt(2.0 * r / divisor);
for (long p = lower; p * p <= 2 * r / divisor; p++) {
long q = (long)Math.sqrt(2.0 * r / divisor - p * p);
// check if q is integer
if (p * p + q * q != 2 * r / divisor) continue;
// ensure p^2 and q^2 have no common divisor
if (gcd(p * p, q * q) == 1) {
long m = divisor * p * q;
long n = r - p * p * divisor;
List<Point> points = new ArrayList<Point>();
points.add(new Point(m + x0, n + y0));
points.add(new Point(m + x0, -1 * n + y0));
points.add(new Point(-1 * m + x0, n + y0));
points.add(new Point(-1 * m + x0, -1 * n + y0));
for (Point point : points) {
updateAns(point, res);
}
}
}
}

// axis point check
List<Point> axis = new ArrayList<Point>();
for (Point point : axis) {
updateAns(point, res);
}
// divide by 1000
res.x /= 1000;
res.y /= 1000;

return res;
}

public static void updateAns(Point p, Point res) {
// point(x, y) in integer
if ((p.x % 1000 == 0) && (p.y % 1000 == 0)) {
if (p.x > res.x) {
res.x = p.x;
res.y = p.y;
} else if (p.x == res.x && p.y > res.y) {
res.y = p.y;
}
}
}

// enumerate all the divisor for n
public static List<Long> getDivisor(long n) {
List<Long> result = new ArrayList<Long>();
for (long i = 1; i * i <= n; i++) {
if (n % i == 0) {
// i * i <= n ==> i <= n / i
if (i != n / i) result.add(n / i);
}
}
Collections.sort(result);
return result;
}

public static long gcd(long a, long b) {
return (b == 0L) ? a : gcd(b, a % b);
}
}

## 题解3 - 勾股数

### Java

import java.io.*;
import java.util.*;
import java.util.Queue;

class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}

class Pythagorean {
long x;
long y;
long z;
Pythagorean(long x, long y, long z) {
this.x = x;
this.y = y;
this.z = z;
}
}

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble();
// convert double to long(accurate)
long x0 = (long)(xd * 1000), y0 = (long)(yd * 1000), r0 = (long)(rd * 1000);
Point result = solve(x0, y0, r0);
System.out.println(result.x + " " + result.y);
}

private static Point solve(long x0, long y0, long r) {
Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE);
long x_max = Long.MIN_VALUE, y_max = Long.MIN_VALUE;
// init
Pythagorean pyth0 = new Pythagorean(3, 4, 5);
q.offer(pyth0);
boolean update = true;
while (!q.isEmpty()) {
int qSize = q.size();
for (int i = 0; i < qSize; i++) {
Pythagorean pyth = q.poll();
if ((r % pyth.z) == 0) {
// System.out.println("x = " + pyth.x + ", y = " + pyth.y + ", r = " + pyth.z);
long k = r / pyth.z;
long kx = k * pyth.x;
long ky = k * pyth.y;
List<Point> points = new ArrayList<Point>();
points.add(new Point(x0 + kx, y0 + ky));
points.add(new Point(x0 - kx, y0 + ky));
points.add(new Point(x0 + kx, y0 - ky));
points.add(new Point(x0 - kx, y0 - ky));
if (kx != ky) {
points.add(new Point(y0 + ky, x0 + kx));
points.add(new Point(y0 - ky, x0 + kx));
points.add(new Point(y0 + ky, x0 - kx));
points.add(new Point(y0 - ky, x0 - kx));
}
for (Point point : points) {
updateAns(point, res);
}
}
for (Pythagorean p : nextPyths(pyth)) {
if (p.z > r) continue;
q.offer(p);
}
}
}

// axis point check
List<Point> axis = new ArrayList<Point>();
for (Point point : axis) {
updateAns(point, res);
}
// divide by 1000
res.x /= 1000;
res.y /= 1000;

return res;
}

public static List<Pythagorean> nextPyths(Pythagorean pyth) {
List<Pythagorean> pyths = new ArrayList<Pythagorean>();
// method 1
Pythagorean pyth1 = new Pythagorean(0, 0, 0);
pyth1.x = pyth.x - 2 * pyth.y + 2 * pyth.z;
pyth1.y = 2 * pyth.x - 1 * pyth.y + 2 * pyth.z;
pyth1.z = 2 * pyth.x - 2 * pyth.y + 3 * pyth.z;
// method 2
Pythagorean pyth2 = new Pythagorean(0, 0, 0);
pyth2.x = pyth.x + 2 * pyth.y + 2 * pyth.z;
pyth2.y = 2 * pyth.x + 1 * pyth.y + 2 * pyth.z;
pyth2.z = 2 * pyth.x + 2 * pyth.y + 3 * pyth.z;
// method 3
Pythagorean pyth3 = new Pythagorean(0, 0, 0);
pyth3.x = -1 * pyth.x + 2 * pyth.y + 2 * pyth.z;
pyth3.y = -2 * pyth.x + pyth.y + 2 * pyth.z;
pyth3.z = -2 * pyth.x + 2 * pyth.y + 3 * pyth.z;

return pyths;
}

public static void updateAns(Point p, Point res) {
// point(x, y) in integer
if ((p.x % 1000 == 0) && (p.y % 1000 == 0)) {
if (p.x > res.x) {
res.x = p.x;
res.y = p.y;
} else if (p.x == res.x && p.y > res.y) {
res.y = p.y;
}
}
}
}