아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

잔디밭

면접 대비

시간 제한2초메모리 제한512 MB

요약
축에 평행한 직사각형 안의 격자점 중 주어진 점에서 거리가 r 이하인 점의 개수를 센다.
난이도

보통10점 중 6점

유형
수학, 기하, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

농부 이반은 어릴 때부터 자기 잔디밭을 살뜰히 가꿔 왔다. 잔디밭은 평면으로 볼 수 있고, 좌표가 모두 정수인 각 점에 풀 한 포기가 자란다.

어느 일요일에 이반은 잔디 깎는 기계로 잔디밭의 직사각형 구역 하나를 깎았다. 이 구역의 변은 좌표축에 평행하고, 서로 마주 보는 두 꼭짓점은 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)에 있다. 이 직사각형의 경계에 있는 풀도 함께 깎였다.

결과에 만족한 이반은 잔디밭에 살수 장치를 사서 설치했다. 장치는 좌표 (x3,y3)(x_3, y_3)에 놓였고 물줄기의 사거리는 rr이었다. 그래서 장치는 (x3,y3)(x_3, y_3)까지의 거리가 rr 이하인 모든 풀에 물을 주기 시작했다. 그런데 이반은 다음이 궁금해졌다. 그 일요일에 깎이면서 동시에 물을 받은 풀은 모두 몇 포기일까?

이반의 질문에 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 네 개 x1,y1,x2,y2x_1, y_1, x_2, y_2가 주어진다 (−100 000≤x1<x2≤100 000-100\,000 \le x_1 < x_2 \le 100\,000; −100 000≤y1<y2≤100 000-100\,000 \le y_1 < y_2 \le 100\,000).

둘째 줄에 정수 세 개 x3,y3,rx_3, y_3, r이 주어진다 (−100 000≤x3,y3≤100 000-100\,000 \le x_3, y_3 \le 100\,000; 1≤r≤100 0001 \le r \le 100\,000).

출력

깎이면서 동시에 물을 받은 풀의 수를 나타내는 정수 하나를 출력한다.

힌트

예제1

  1. 예제 1

    입력
    0 0 5 4
    4 0 3
    
    예상 출력
    14