시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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 연산자.)

제한 사항

  • 입력되는 모든 숫자는 정수이다.
  • -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+ajxcL3N1Yj5cdWM3NzQgTiBcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMxXHVjMTIwXHVhY2ZjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNTBcdWM4MTBcdWM3NTggeCBcdWM4OGNcdWQ0NWMgXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0MCBcdWJiMzRcdWM1YzdcdWM3NzhcdWFjMDA/JiMzOTtcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMThcdWM5YzFcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOIFx1YzkwNFx1YjljOFx1YjJlNCBcdWJjMThcdWM5YzFcdWMxMjAgXHViYzI5XHVjODE1XHVjMmRkXHVjNzU4IFx1YWNjNFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1ZDBjMFx1YjA5OFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBRIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBFLCBGXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzljMVx1YzgwNCBcdWM5YzhcdWJiMzhcdWM3NTggXHVjOWMxXHVjMTIwKHkgPSBDPHN1Yj5qLTE8XC9zdWI+KnggKyBEPHN1Yj5qLTE8XC9zdWI+KVx1Yzc3NCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzFcdWMxMjBcdWFjZmMgXHVjNzc0XHViOGU4XHViMjk0IFx1YWQ1MFx1YzgxMFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3ODhcdWM1YzhcdWFjNzBcdWIwOTggXHVjNzc0XHVhYzgzXHVjNzc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOWM4XHViYjM4XHVjNzc0XHViNzdjXHViYTc0IEM8c3ViPmo8XC9zdWI+ID0gRSwgRDxzdWI+ajxcL3N1Yj4gPSBGIFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBDPHN1Yj5qPFwvc3ViPiA9IEUgXiAoMjxzdXA+Mjk8XC9zdXA+LTEpIGFuZCBEPHN1Yj5qPFwvc3ViPiA9IEYgXiAoMjxzdXA+Mjk8XC9zdXA+LTEpIFx1Yzc3NFx1YjJlNC4gKF5cdWIyOTQgWE9SIFx1YzVmMFx1YzBiMFx1Yzc5MC4pPFwvcD5cclxuXHJcbjxwPlx1YzgxY1x1ZDU1YyBcdWMwYWNcdWQ1NmQ8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3ODVcdWI4MjVcdWI0MThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPi0yMDAwMDAwMDAwICZsdDsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiwgRDxzdWI+aTxcL3N1Yj4gJmx0OyAyMDAwMDAwMDAwPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBpLCBqIChpJm5lO2opXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBBPHN1Yj5pPFwvc3ViPiZuZTtBPHN1Yj5qPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT5cdWM3ODRcdWM3NThcdWM3NTggaSwgalx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgQTxzdWI+aTxcL3N1Yj4mbmU7QzxzdWI+ajxcL3N1Yj48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IGksIGpcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIEI8c3ViPmk8XC9zdWI+Jm5lO0Q8c3ViPmo8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjAgJmx0OyBOLCBRICZsdDsgNTAwMDE8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlFcdWFjMWNcdWM3NTggXHVjOWM4XHViYjM4XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMmU0XHVjMjE4IHhcdWI5N2MgXHVjMThjXHVjMjE4XHVjODEwIFx1Yzc3NFx1ZDU1OCBcdWM4MDFcdWM1YjRcdWIzYzQgNlx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIHhcdWIyOTQgXHVjOWM4XHViYjM4XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM5YzFcdWMxMjBcdWM3NzQgTiBcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMxXHVjMTIwXHVhY2ZjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkNTBcdWM4MTBcdWM3NTggeCBcdWM4OGNcdWQ0NWMgXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzljMVx1YzEyMFx1Yzc3NCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzFcdWMxMjBcdWFjZmMgXHVjNzc0XHViOGU4XHViMjk0IFx1YWQ1MFx1YzgxMFx1Yzc3NCBcdWQ1NThcdWIwOThcdWIzYzQgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90O05vIGNyb3NzJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwNTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBOIHJheXMgKGhhbGYtbGluZXMpIHdpdGggaW5pdGlhbCBwb2ludHMgb24gdGhlIE95IGF4aXMuIE5vbmUgb2YgdGhlIHJheXMgaXMgcGFyYWxsZWwgdG8gdGhlIE95IGF4aXMuIFRoZSByYXlzIGFyZSBnaXZlbiBpbiB0aGUgZm9ybSB5ID0gQTxzdWI+aTxcL3N1Yj4qeCArIEI8c3ViPmk8XC9zdWI+LiBFYWNoIHJheSBpcyBvbmx5IGRlZmluZWQgZm9yIHBvc2l0aXZlIHguPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSBsaW5lcyB0aGF0IGFuc3dlcnMgUSBxdWVyaWVzIG9mIHRoZSB0eXBlOiBXaGF0IGlzIHRoZSBtYXhpbWFsIHhjb29yZGluYXRlIG9mIGFuIGludGVyc2VjdGlvbiBwb2ludCBvZiB0aGUgbGluZSB5ID0gQzxzdWI+ajxcL3N1Yj4qeCArIEQ8c3ViPmo8XC9zdWI+Jm5ic3A7d2l0aCBvbmUgb2YgdGhlIGdpdmVuIE4gcmF5cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBpcyBnaXZlbiBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgdGhlIHJheXMuIE9uIGVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBhcmUgZ2l2ZW4gdGhlIHR3byBpbnRlZ2VyczogQTxzdWI+aTxcL3N1Yj4mbmJzcDthbmQgQjxzdWI+aTxcL3N1Yj4sIHRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGVxdWF0aW9uIG9mIGVhY2ggcmF5LiBPbiB0aGUgbmV4dCBsaW5lIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgUSBpcyBnaXZlbiwgdGhlIG51bWJlciBvZiBxdWVyaWVzLiBPbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgUSBsaW5lcyBhcmUgZ2l2ZW4gdHdvIGludGVnZXJzIEUgYW5kIEYuIElmIHRoZSBwcmV2aW91cyBsaW5lIGhhZCBjcm9zc2VkIG9uZSBvZiB0aGUgcmF5cywgb3IgaWYgdGhpcyBpcyB0aGUgZmlyc3QgbGluZSwgdGhlc2UgYXJlIHRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGVxdWF0aW9uIG9mIHRoZSBjdXJyZW50IGxpbmUgKEM8c3ViPmo8XC9zdWI+Jm5ic3A7PSBFLCBEPHN1Yj5qPFwvc3ViPiZuYnNwOz0gRikuIE90aGVyd2lzZSwgdGhlIGNvZWZmaWNpZW50cyBvZiB0aGUgZXF1YXRpb24gb2YgdGhlIGxpbmUgYXJlIEM8c3ViPmo8XC9zdWI+Jm5ic3A7PSBFIF4gKDI8c3VwPjI5PFwvc3VwPi0xKSBhbmQgRDxzdWI+ajxcL3N1Yj4mbmJzcDs9IEYgXiAoMjxzdXA+Mjk8XC9zdXA+LTEpLCB3aGVyZSBeIGlzIHRoZSBYT1Igb3BlcmF0aW9uLjxcL3A+XHJcblxyXG48cD5Db25zdHJhaW50czxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkFsbCB0aGUgbnVtYmVycyBpbiB0aGUgaW5wdXQgYXJlIGludGVnZXJzLjxcL2xpPlxyXG5cdDxsaT4tMjAwMDAwMDAwMCAmbHQ7IEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiwgQzxzdWI+aTxcL3N1Yj4sIEQ8c3ViPmk8XC9zdWI+Jm5ic3A7Jmx0OyAyMDAwMDAwMDAwPFwvbGk+XHJcblx0PGxpPkFsbCBudW1iZXJzIEE8c3ViPmk8XC9zdWI+Jm5ic3A7YXJlIGRpZmZlcmVudC48XC9saT5cclxuXHQ8bGk+RWFjaCBDPHN1Yj5qPFwvc3ViPiZuYnNwO2lzIGRpZmZlcmVudCBmcm9tIGFueSBvZiB0aGUgbnVtYmVycyBBPHN1Yj5pPFwvc3ViPi48XC9saT5cclxuXHQ8bGk+RWFjaCBEPHN1Yj5qPFwvc3ViPiZuYnNwO2lzIGRpZmZlcmVudCBmcm9tIGFueSBvZiB0aGUgbnVtYmVycyBCPHN1Yj5pPFwvc3ViPi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+MCAmbHQ7IE4sIFEgJmx0OyA1MDAwMSZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlc3Rpb24gb3V0cHV0IGEgc2luZ2xlIHJlYWwgbnVtYmVyIHggd2l0aCBhdCBsZWFzdCA2IGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludCwgdGhlIG1heGltYWwgeC1jb29yZGluYXRlIG9mIGEgcG9pbnQgaW4gd2hpY2ggdGhlIGN1cnJlbnQgbGluZSBjcm9zc2VzIG9uZSBvZiB0aGUgZ2l2ZW4gcmF5cy4gSWYgdGhlIGxpbmUgZG9lc24mIzM5O3QgY3Jvc3MgYW55IHJheSwgb3V0cHV0ICZxdW90O05vIGNyb3NzJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Tournament in Informatics > Shumen 2012 A3번