스칼라 곱

시간 제한3초메모리 제한1024 MB

요약

정수 a, b, R이 주어질 때 x^2 + y^2 <= R^2을 만족하는 정수 점 (x, y)와 벡터 (a, b)의 내적 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

정수 $a$ , $b$ , $R$ 이 주어진다. 벡터 $(a,b)$ 에 대해 $x^2+y^2 \le R^2$ 을 만족하는 모든 정수 쌍 $(x,y)$ 중에서 스칼라 곱 $(a,b) \cdot (x,y)$ 의 최댓값을 구한다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다 ( $1 \le T \le 1\,000$ ). 이어서 $T$ 개의 줄에 정수 $a$ , $b$ , $R$ 이 각각 주어진다 ( $-10^9 \le a,b \le 10^9$ , $1 \le R \le 10^9$ ).

출력

각 테스트 케이스마다 스칼라 곱의 최댓값을 한 줄에 하나씩 출력한다.

힌트

첫 번째 테스트 케이스에서 $x^2+y^2 \le R^2$ 을 만족하는 정수점은 13개이다. 이 중 $(2,0)$ , $(1,-1)$ , $(0,-2)$ 세 점이 $(10,-10)$ 과의 스칼라 곱을 최대로 만든다. 예를 들어 $10 \times 1 + (-10) \times (-1) = 20$ 이다.

예제1

예제 1
입력
```
3
10 -10 2
2 3 3
5 1 3
```
예상 출력
```
20
10
15
```