시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 51 | 8 | 6 | 17.143% |
N개의 반직선이 있다. 각 반직선의 시작점은 y축 선상에 있고, y축과 평행한 반직선은 없다. 각 반직선은 y=Ai*x+Bi의 꼴로 주어진다. 각 반직선은 양수 x에 대해서만 정의된다.
Q개의 질문에 답을 하는 문제를 작성하라. 각 질문은 '직선 y=Cj*x + Dj이 N 개의 반직선과 이루는 교점의 x 좌표 값의 최댓값은 무엇인가?'이다.
입력 첫 줄에는 반직선의 개수를 나타내는 자연수 N이 주어진다. 다음 N 줄마다 반직선 방정식의 계수를 나타내는 두 개의 정수 Ai, Bi가 주어진다. 다음 줄에는 문제의 개수를 타나내는 자연수 Q가 주어진다. 다음 Q 줄에는 두 개의 정수 E, F가 주어진다. 만약 직전 질문의 직선(y = Cj-1*x + Dj-1)이 N 개의 반직선과 이루는 교점이 적어도 한 개 있었거나 이것이 첫 번째 질문이라면 Cj = E, Dj = F 이다. 그렇지 않으면 Cj = E ^ (229-1) and Dj = F ^ (229-1) 이다. (^는 XOR 연산자.)
Q개의 질문에 대하여 하나의 실수 x를 소수점 이하 적어도 6자리까지 출력하라. x는 질문에서 주어진 직선이 N 개의 반직선과 이루는 교점의 x 좌표 값의 최댓값이다. 만약 직선이 N 개의 반직선과 이루는 교점이 하나도 없다면 "No cross"를 출력하라.
2 4 2 -1 0 3 -5 3 0 1 -5 3
0.75000000 No cross 1.00000000
Olympiad > International Autumn Tournament in Informatics > 2012 > Group A (Seniors) 3번