2053번 - 반직선 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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,000,000,000 < Ai, Bi, Ci, Di < 2,000,000,000
- 임의의 i, j (i ≠ j)에 대하여 Ai ≠ Aj
- 임의의 i, j에 대하여 Ai ≠ Cj
- 임의의 i, j에 대하여 Bi ≠ Dj
- 1 ≤ N, Q ≤ 50,000
예제 입력 1
2 4 2 -1 0 3 -5 3 0 1 -5 3
예제 출력 1
0.75000000 No cross 1.00000000
출처
Olympiad > International Autumn Tournament in Informatics > 2012 > Group A (Seniors) 3번
- 잘못된 조건을 찾은 사람: koosaga
- 문제의 오타를 찾은 사람: sgc109
- 문제를 번역한 사람: thebarbershop
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호