무선 네트워크

면접 대비

시간 제한1초메모리 제한128 MB

요약

격자 교차점에 정수 중심과 정수 반지름을 가진 K개의 원이 주어질 때, 어떤 교차점이 받는 비트레이트 합의 최댓값과 그 최댓값을 얻는 교차점 수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 구현, 완전 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

밥(Bob)은 집에서 컴퓨터와 함께 지내고 있다. 더 많은 사람들과 어울리고 싶었던 그는 노트북을 들고 카페에 가기로 했다.

밥이 사는 도시에서는 거리의 모든 교차로마다 카페가 하나씩 있다. 이 도시에는 동서 방향으로 뻗은 거리가 $M$ 개 ( $1 \le M \le 30000$ ), 남북 방향으로 뻗은 거리가 $N$ 개 ( $1 \le N \le 1000$ ) 있다. 인접한 평행 거리 사이의 간격은 모두 1미터이다(매우 촘촘한 도시이다).

그중 $K$ 개 ( $1 \le K \le 1000$ )의 카페 안에는 무선 네트워크 공유기가 설치되어 있다. 각 공유기는 비트레이트 $B$ ( $1 \le B \le 1000$ )를 제공하며, 카페로부터 $R$ 미터 ( $1 \le R \le 30000$ ) 떨어진 곳까지 신호가 닿는다. 즉, 하나의 공유기는 그 카페를 중심으로 반지름이 $R$ 인 원 모양의 영역을 덮는다. 어떤 지점까지의 거리가 정확히 $R$ 이면 신호를 사용할 수 있지만, 거리가 $R$ 보다 크면 사용할 수 없다.

각 카페에는 공유기가 최대 하나만 설치되지만, 가까운 다른 카페의 공유기 신호가 닿는다면 한 카페에서 여러 무선 네트워크를 동시에 사용할 수도 있다.

밥의 컴퓨터에는 연결할 수 있는 모든 무선 네트워크의 비트레이트를 한꺼번에 합쳐서 사용하는 특별한 장치가 있다.

밥은 얻을 수 있는 최대 비트레이트가 얼마인지, 그리고 그 최대 비트레이트를 얻을 수 있는 카페가 몇 곳인지 알고 싶어한다.

입력

첫째 줄에 동서 방향 거리의 수 $M$ 이 주어진다. 둘째 줄에 남북 방향 거리의 수 $N$ 이 주어진다. 셋째 줄에 무선 네트워크가 있는 카페의 수 $K$ 가 주어진다. 이어지는 $K$ 개의 줄에는 각각 네 개의 정수가 주어진다. 첫 번째 정수 $x$ 는 카페가 위치한 남북 방향 거리의 번호로 $1 \le x \le N$ 이다. 두 번째 정수 $y$ 는 카페가 위치한 동서 방향 거리의 번호로 $1 \le y \le M$ 이다. 세 번째 정수 $R$ 은 그 카페 무선 네트워크의 반지름이다. 네 번째 정수 $B$ 는 그 카페 무선 네트워크의 비트레이트이다.

출력

출력은 두 줄이다. 첫째 줄에는 모든 카페(교차로) 중에서 얻을 수 있는 최대 비트레이트를 정수로 출력한다. 둘째 줄에는 그 최대 비트레이트를 얻을 수 있는 카페의 수를 출력한다.

힌트

아래 그림에서 진한 원으로 표시된 다섯 개의 카페(교차로)는 모두 비트레이트의 합이 12이다.

예제5

예제 1
입력
```
3
5
3
1 3 2 5
3 1 2 7
5 1 1 5
```
예상 출력
```
12
5
```
예제 2
입력
```
1
1
1
1 1 1 10
```
예상 출력
```
10
1
```
예제 3
입력
```
1
1
2
1 1 1 3
1 1 1 4
```
예상 출력
```
7
1
```
예제 4
입력
```
1
3
1
2 1 1 5
```
예상 출력
```
5
3
```
예제 5
입력
```
1
5
2
2 1 1 3
4 1 1 4
```
예상 출력
```
7
1
```