사격
시간 제한1초메모리 제한512 MB
겹치지 않는 축 정렬 직사각형들과 수직 또는 45도 반직선 발사가 주어질 때, 각 발사가 모든 직사각형과 만나는 길이의 합의 제곱을 구한다.
문제
Mihai는 한동안 군사 훈련을 받았고 아직 휴가를 받지 못했기 때문에, 상관인 Dan 대위에게 다시 한 번 운을 시험해 보기로 했다. Dan은 이번에는 조금 더 친절했지만, 먼저 자신의 사격 실력을 증명해 보라고 했다.
사격장의 과녁은 평면 위의 직사각형으로 생각할 수 있다. 대위는 Mihai에게 OX 축 위의 몇몇 점과 발사할 방향을 알려준다. 각 발사는 반직선이며, 45도 왼쪽 대각선, 45도 오른쪽 대각선, 수직 중 한 방향으로 향한다.
한 발사가 어떤 과녁을 맞힐 때의 비용은 발사의 반직선과 과녁 직사각형의 교집합의 길이로 정의한다. 교집합이 공집합이거나 한 점으로 이루어진 경우 비용은 0이다. 한 발사의 비용은 모든 과녁에 대한 발사의 명중 비용의 합으로 정의한다. 각 발사의 비용을 구하시오.
입력
표준 입력의 첫 줄에는 과녁 직사각형의 개수 N이 주어진다. 다음 N개 줄에는 각각 과녁 직사각형을 정의하는 4개의 자연수 X1, Y1, X2, Y2가 공백으로 구분되어 주어지며, 각각 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표를 나타낸다. 그다음 줄에는 발사의 개수 T가 주어진다. 다음 T개 줄에는 Mihai가 발사하는 점의 X 좌표 P와 발사 방향 D가 공백으로 구분되어 주어진다(D = 1은 수직 발사, D = 2는 왼쪽 대각선 발사, D = 3은 오른쪽 대각선 발사를 나타낸다).
출력
표준 출력에는 입력에 나타난 순서대로, 각 발사의 제곱 비용을 나타내는 음이 아닌 정수 T개가 한 줄에 하나씩 주어진다. 즉, 구한 각 비용에 대해 그 값의 제곱을 출력해야 한다.
제한
- 1 ≤ N ≤ 50000
- 1 ≤ T ≤ 100000
- 1 ≤ X1 < X2 ≤ 100000, 1 ≤ Y1 < Y2 ≤ 100000
- -100000 ≤ P ≤ 200000
- 모든 직사각형의 변은 OX 축과 OY 축에 평행하다
- 두 직사각형은 교차하지 않으며(즉, 공통점이 없다), 한 직사각형이 다른 직사각형에 완전히 포함되는 경우도 없다
- 직사각형은 정사각형일 수 있다
- 직사각형의 넓이는 0이 아니다
- 동일한 발사가 있을 수 있다
- 출력되는 수는 항상 음이 아닌 정수이다
힌트
첫 번째 발사의 비용은 (2√2 + √2)2=18이다.
두 번째 발사의 비용은 (1 + 2)2 = 9이다.