시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 49 6 4 12.121%

문제

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 연산자.)

제한 사항

  • 입력되는 모든 숫자는 정수이다.
  • -2000000000 < Ai, Bi, Ci, Di < 2000000000
  • 임의의 i, j (i≠j)에 대하여 Ai≠Aj
  • 임의의 i, j에 대하여 Ai≠Cj
  • 임의의 i, j에 대하여 Bi≠Dj
  • 0 < N, Q < 50001

출력

Q개의 질문에 대하여 하나의 실수 x를 소수점 이하 적어도 6자리까지 출력하라. x는 질문에서 주어진 직선이 N 개의 반직선과 이루는 교점의 x 좌표 값의 최대값이다. 만약 직선이 N 개의 반직선과 이루는 교점이 하나도 없다면 "No cross"를 출력하라.

예제 입력 1

2
4 2
-1 0
3
-5 3
0 1
-5 3

예제 출력 1

0.75000000 
No cross 
1.00000000
W3sicHJvYmxlbV9pZCI6IjIwNTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWM5YzFcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPk4gXHVhYzFjXHVjNzU4IFx1YmMxOFx1YzljMVx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWJjMThcdWM5YzFcdWMxMjBcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVjNzQwIHlcdWNkOTUgXHVjMTIwXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YWNlMCwgeVx1Y2Q5NVx1YWNmYyBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHViYzE4XHVjOWMxXHVjMTIwXHVjNzQwIFx1YzVjNlx1YjJlNC4gXHVhYzAxIFx1YmMxOFx1YzljMVx1YzEyMFx1Yzc0MCB5PUE8c3ViPmk8XC9zdWI+KngrQjxzdWI+aTxcL3N1Yj5cdWM3NTggXHVhZjM0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmMxOFx1YzljMVx1YzEyMFx1Yzc0MCBcdWM1OTFcdWMyMTggeFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWI5Y2MgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5RXHVhYzFjXHVjNzU4IFx1YzljOFx1YmIzOFx1YzVkMCBcdWIyZjVcdWM3NDQgXHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuIFx1YWMwMSBcdWM5YzhcdWJiMzhcdWM3NDAgJiMzOTtcdWM5YzFcdWMxMjAgeT1DPHN1Yj5qPFwvc3ViPip4ICsgRDxzdWI+ajxcL3N1Yj5cdWM3NzQgTiBcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMxXHVjMTIwXHVhY2ZjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNTBcdWM4MTBcdWM3NTggeCBcdWM4OGNcdWQ0NWMgXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0MCBcdWJiMzRcdWM1YzdcdWM3NzhcdWFjMDA/JiMzOTtcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMThcdWM5YzFcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOIFx1YzkwNFx1YjljOFx1YjJlNCBcdWJjMThcdWM5YzFcdWMxMjAgXHViYzI5XHVjODE1XHVjMmRkXHVjNzU4IFx1YWNjNFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1ZDBjMFx1YjA5OFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBRIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBFLCBGXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzljMVx1YzgwNCBcdWM5YzhcdWJiMzhcdWM3NTggXHVjOWMxXHVjMTIwKHkgPSBDPHN1Yj5qLTE8XC9zdWI+KnggKyBEPHN1Yj5qLTE8XC9zdWI+KVx1Yzc3NCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzFcdWMxMjBcdWFjZmMgXHVjNzc0XHViOGU4XHViMjk0IFx1YWQ1MFx1YzgxMFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3ODhcdWM1YzhcdWFjNzBcdWIwOTggXHVjNzc0XHVhYzgzXHVjNzc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOWM4XHViYjM4XHVjNzc0XHViNzdjXHViYTc0IEM8c3ViPmo8XC9zdWI+ID0gRSwgRDxzdWI+ajxcL3N1Yj4gPSBGIFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBDPHN1Yj5qPFwvc3ViPiA9IEUgXiAoMjxzdXA+Mjk8XC9zdXA+LTEpIGFuZCBEPHN1Yj5qPFwvc3ViPiA9IEYgXiAoMjxzdXA+Mjk8XC9zdXA+LTEpIFx1Yzc3NFx1YjJlNC4gKF5cdWIyOTQgWE9SIFx1YzVmMFx1YzBiMFx1Yzc5MC4pPFwvcD5cclxuXHJcbjxwPlx1YzgxY1x1ZDU1YyBcdWMwYWNcdWQ1NmQ8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3ODVcdWI4MjVcdWI0MThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPi0yMDAwMDAwMDAwICZsdDsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiwgRDxzdWI+aTxcL3N1Yj4gJmx0OyAyMDAwMDAwMDAwPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBpLCBqIChpJm5lO2opXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBBPHN1Yj5pPFwvc3ViPiZuZTtBPHN1Yj5qPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT5cdWM3ODRcdWM3NThcdWM3NTggaSwgalx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgQTxzdWI+aTxcL3N1Yj4mbmU7QzxzdWI+ajxcL3N1Yj48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IGksIGpcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIEI8c3ViPmk8XC9zdWI+Jm5lO0Q8c3ViPmo8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjAgJmx0OyBOLCBRICZsdDsgNTAwMDE8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlFcdWFjMWNcdWM3NTggXHVjOWM4XHViYjM4XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMmU0XHVjMjE4IHhcdWI5N2MgXHVjMThjXHVjMjE4XHVjODEwIFx1Yzc3NFx1ZDU1OCBcdWM4MDFcdWM1YjRcdWIzYzQgNlx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIHhcdWIyOTQgXHVjOWM4XHViYjM4XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM5YzFcdWMxMjBcdWM3NzQgTiBcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMxXHVjMTIwXHVhY2ZjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNTBcdWM4MTBcdWM3NTggeCBcdWM4OGNcdWQ0NWMgXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzljMVx1YzEyMFx1Yzc3NCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzFcdWMxMjBcdWFjZmMgXHVjNzc0XHViOGU4XHViMjk0IFx1YWQ1MFx1YzgxMFx1Yzc3NCBcdWQ1NThcdWIwOThcdWIzYzQgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90O05vIGNyb3NzJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMDUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gTiByYXlzIChoYWxmLWxpbmVzKSB3aXRoIGluaXRpYWwgcG9pbnRzIG9uIHRoZSBPeSBheGlzLiBOb25lIG9mIHRoZSByYXlzIGlzIHBhcmFsbGVsIHRvIHRoZSBPeSBheGlzLiBUaGUgcmF5cyBhcmUgZ2l2ZW4gaW4gdGhlIGZvcm0geSA9IEE8c3ViPmk8XC9zdWI+KnggKyBCPHN1Yj5pPFwvc3ViPi4gRWFjaCByYXkgaXMgb25seSBkZWZpbmVkIGZvciBwb3NpdGl2ZSB4LjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gbGluZXMgdGhhdCBhbnN3ZXJzIFEgcXVlcmllcyBvZiB0aGUgdHlwZTogV2hhdCBpcyB0aGUgbWF4aW1hbCB4Y29vcmRpbmF0ZSBvZiBhbiBpbnRlcnNlY3Rpb24gcG9pbnQgb2YgdGhlIGxpbmUgeSA9IEM8c3ViPmo8XC9zdWI+KnggKyBEPHN1Yj5qPFwvc3ViPiZuYnNwO3dpdGggb25lIG9mIHRoZSBnaXZlbiBOIHJheXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgaXMgZ2l2ZW4gYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIHRoZSByYXlzLiBPbiBlYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgYXJlIGdpdmVuIHRoZSB0d28gaW50ZWdlcnM6IEE8c3ViPmk8XC9zdWI+Jm5ic3A7YW5kIEI8c3ViPmk8XC9zdWI+LCB0aGUgY29lZmZpY2llbnRzIG9mIHRoZSBlcXVhdGlvbiBvZiBlYWNoIHJheS4gT24gdGhlIG5leHQgbGluZSBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIFEgaXMgZ2l2ZW4sIHRoZSBudW1iZXIgb2YgcXVlcmllcy4gT24gZWFjaCBvZiB0aGUgZm9sbG93aW5nIFEgbGluZXMgYXJlIGdpdmVuIHR3byBpbnRlZ2VycyBFIGFuZCBGLiBJZiB0aGUgcHJldmlvdXMgbGluZSBoYWQgY3Jvc3NlZCBvbmUgb2YgdGhlIHJheXMsIG9yIGlmIHRoaXMgaXMgdGhlIGZpcnN0IGxpbmUsIHRoZXNlIGFyZSB0aGUgY29lZmZpY2llbnRzIG9mIHRoZSBlcXVhdGlvbiBvZiB0aGUgY3VycmVudCBsaW5lIChDPHN1Yj5qPFwvc3ViPiZuYnNwOz0gRSwgRDxzdWI+ajxcL3N1Yj4mbmJzcDs9IEYpLiBPdGhlcndpc2UsIHRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGVxdWF0aW9uIG9mIHRoZSBsaW5lIGFyZSBDPHN1Yj5qPFwvc3ViPiZuYnNwOz0gRSBeICgyPHN1cD4yOTxcL3N1cD4tMSkgYW5kIEQ8c3ViPmo8XC9zdWI+Jm5ic3A7PSBGIF4gKDI8c3VwPjI5PFwvc3VwPi0xKSwgd2hlcmUgXiBpcyB0aGUgWE9SIG9wZXJhdGlvbi48XC9wPlxyXG5cclxuPHA+Q29uc3RyYWludHM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BbGwgdGhlIG51bWJlcnMgaW4gdGhlIGlucHV0IGFyZSBpbnRlZ2Vycy48XC9saT5cclxuXHQ8bGk+LTIwMDAwMDAwMDAgJmx0OyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+LCBEPHN1Yj5pPFwvc3ViPiZuYnNwOyZsdDsgMjAwMDAwMDAwMDxcL2xpPlxyXG5cdDxsaT5BbGwgbnVtYmVycyBBPHN1Yj5pPFwvc3ViPiZuYnNwO2FyZSBkaWZmZXJlbnQuPFwvbGk+XHJcblx0PGxpPkVhY2ggQzxzdWI+ajxcL3N1Yj4mbmJzcDtpcyBkaWZmZXJlbnQgZnJvbSBhbnkgb2YgdGhlIG51bWJlcnMgQTxzdWI+aTxcL3N1Yj4uPFwvbGk+XHJcblx0PGxpPkVhY2ggRDxzdWI+ajxcL3N1Yj4mbmJzcDtpcyBkaWZmZXJlbnQgZnJvbSBhbnkgb2YgdGhlIG51bWJlcnMgQjxzdWI+aTxcL3N1Yj4uJm5ic3A7PFwvbGk+XHJcblx0PGxpPjAgJmx0OyBOLCBRICZsdDsgNTAwMDEmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXN0aW9uIG91dHB1dCBhIHNpbmdsZSByZWFsIG51bWJlciB4IHdpdGggYXQgbGVhc3QgNiBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQsIHRoZSBtYXhpbWFsIHgtY29vcmRpbmF0ZSBvZiBhIHBvaW50IGluIHdoaWNoIHRoZSBjdXJyZW50IGxpbmUgY3Jvc3NlcyBvbmUgb2YgdGhlIGdpdmVuIHJheXMuIElmIHRoZSBsaW5lIGRvZXNuJiMzOTt0IGNyb3NzIGFueSByYXksIG91dHB1dCAmcXVvdDtObyBjcm9zcyZxdW90Oy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Tournament in Informatics > Shumen 2012 A3번