반직선
시간 제한2초메모리 제한128 MB
y축에서 시작하는 N개의 반직선이 주어질 때, 이전 질의 결과에 따라 XOR로 값이 바뀌는 온라인 질의마다 질의 직선이 반직선들과 만나는 최대 x좌표를 구해야 합니다.
문제
N개의 반직선이 주어진다. 각 반직선은 y축 위의 점에서 시작하며, y축과 평행하지 않다. i번째 반직선은 직선 y = A_i x + B_i 중 x > 0인 부분이다.
Q개의 질문에 답하라. j번째 질문에서 주어진 직선 y = C_j x + D_j와 N개의 반직선이 만나는 점들을 모두 생각한다. 그 교점들의 x좌표 중 최댓값을 구하라.
입력
첫 줄에 반직선의 개수 N이 주어진다. 다음 N줄에는 각 반직선의 계수 A_i, B_i가 공백으로 구분되어 주어진다.
그다음 줄에 질문의 개수 Q가 주어진다. 다음 Q줄에는 두 정수 E, F가 주어진다.
현재 질문이 첫 번째 질문이거나, 직전 질문의 직선과 N개의 반직선 사이에 교점이 하나 이상 있었다면 C_j = E, D_j = F이다. 그렇지 않다면 C_j = E XOR (2^29 - 1), D_j = F XOR (2^29 - 1)이다. 여기서 XOR는 비트 단위 배타적 논리합 연산이다.
출력
각 질문마다 한 줄에 답을 출력한다. 답은 질문에서 주어진 직선과 N개의 반직선이 이루는 교점들의 x좌표 중 최댓값이며, 소수점 아래 적어도 6자리까지 출력해야 한다.
교점이 하나도 없다면 No cross를 출력한다.
제한
- 입력되는 모든 값은 정수이다.
- -2,000,000,000 < A_i, B_i, C_j, D_j < 2,000,000,000
- 모든 i, j (i ≠ j)에 대해 A_i ≠ A_j
- 모든 i, j에 대해 A_i ≠ C_j
- 모든 i, j에 대해 B_i ≠ D_j
- 1 ≤ N, Q ≤ 50,000