시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 783 161 112 24.670%

문제

이제 사각형의 경계선과 선분의 교차점에 관한 간단한 기하 문제를 풀어볼 것이다.

매우 다행히도 사각형은 항상 축에 평행한 형태로만 놓여 있다.

어떤 사각형과 어떤 선분의 교차점은 항상 0개이거나, 1개이거나, 2개이거나, 무한하다.

각각의 경우에 대한 몇 가지 예제는 아래와 같다.

(a) 교점이 0개인 경우

(b) 교점이 1개인 경우

(c) 교점이 2개인 경우

(d) 교점이 무한히 많은 경우

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 4개의 정수로 시작한다. 각 정수는 xmin, ymin, xmax, ymax이며, 이것은 사각형의 왼쪽 아래 꼭짓점이 (xmin, ymin)이고 오른쪽 위 꼭짓점이 (xmax, ymax)임을 의미한다. (-10,000 ≤ xmin < xmax ≤ 10,000, -10,000 ≤ ymin < ymax ≤ 10,000그 다음 줄에도 4개의 정수 x1, y1, x2, y2가 주어진다. 이는 선분의 한쪽 끝점이 (x1,y1)이며 다른쪽 끝점이 (x2,y2)임을 의미한다. (-10,000 ≤ x1, y1, x2, y2 ≤ 10,000)

선분의 길이는 항상 0보다 크다.

출력

테스트 케이스마다 하나의 정수를 출력한다.

만일 주어진 사각형과 선분의 교차점의 개수가 유한하다면 교차점의 개수를 출력하고, 교차점이 무한히 많다면 4를 출력한다.

예제 입력 1

16
0 0 8 4
2 6 -2 3
0 0 8 4
0 4 9 4
0 0 8 4
3 5 6 6
0 0 8 4
-2 5 10 -1
0 0 8 4
0 5 8 5
0 0 8 4
4 3 4 1
0 0 8 4
-2 3 2 5
0 0 8 4
2 4 6 4
0 0 8 4
0 4 4 7
0 0 8 4
4 2 4 4
0 0 8 4
4 2 8 4
0 0 8 4
0 2 3 4
0 0 8 4
-4 0 12 4
0 0 8 4
4 8 4 -1
0 0 8 4
0 -2 0 6
0 0 8 4
3 4 10 4

예제 출력 1

0
4
0
2
0
0
1
4
1
1
1
2
2
2
4
4
W3sicHJvYmxlbV9pZCI6IjEwMjU1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDUwXHVjYzI4XHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWM4MWMgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWNiZFx1YWNjNFx1YzEyMFx1YWNmYyBcdWMxMjBcdWJkODRcdWM3NTggXHVhZDUwXHVjYzI4XHVjODEwXHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWFjMDRcdWIyZThcdWQ1NWMgXHVhZTMwXHVkNTU4IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWM1YjRcdWJjZmMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTRcdWM2YjAgXHViMmU0XHVkNTg5XHVkNzg4XHViM2M0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWQ2MTVcdWQwZGNcdWI4NWNcdWI5Y2MgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1YWNmYyBcdWM1YjRcdWI1YTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YWQ1MFx1Y2MyOFx1YzgxMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMFx1YWMxY1x1Yzc3NFx1YWM3MFx1YjA5OCwgMVx1YWMxY1x1Yzc3NFx1YWM3MFx1YjA5OCwgMlx1YWMxY1x1Yzc3NFx1YWM3MFx1YjA5OCwgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJhODcgXHVhYzAwXHVjOWMwIFx1YzYwOFx1YzgxY1x1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvaW50ZXIxLnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oYSkgXHVhZDUwXHVjODEwXHVjNzc0IDBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgc3JjPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvdXBsb2FkXC9pbWFnZXMyXC9pbnRlcjIucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPihiKSBcdWFkNTBcdWM4MTBcdWM3NzQgMVx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjA8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBzcmM9XCJodHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC91cGxvYWRcL2ltYWdlczJcL2ludGVyMy5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+KGMpIFx1YWQ1MFx1YzgxMFx1Yzc3NCAyXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMDxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvaW50ZXI0LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oZCkgXHVhZDUwXHVjODEwXHVjNzc0IFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWM3NDAgXHVhY2JkXHVjNmIwPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgeG1pbiwgeW1pbiwgeG1heCwgeW1heFx1Yzc3NFx1YmE3MCwgXHVjNzc0XHVhYzgzXHVjNzQwIFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCAoeG1pbiwgeW1pbilcdWM3NzRcdWFjZTAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgKHhtYXgsIHltYXgpXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4oLTEwLDAwMCAmbGU7IHhtaW4gJmx0OyB4bWF4ICZsZTsgMTAsMDAwLDxcL3NwYW4+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPiZuYnNwOy0xMCwwMDAgJmxlOyB5bWluICZsdDsgeW1heCAmbGU7IDEwLDAwMDxcL3NwYW4+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPikmbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjNjNCA0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCB4MSwgeTEsIHgyLCB5Mlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvc3Bhbj48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVjNzc0XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWQ1NWNcdWNhYmQgXHViMDVkXHVjODEwXHVjNzc0ICh4MSx5MSlcdWM3NzRcdWJhNzAgXHViMmU0XHViOTc4XHVjYWJkIFx1YjA1ZFx1YzgxMFx1Yzc3NCAoeDIseTIpXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4oLTEwLDAwMCAmbGU7IHgxLCB5MSwgeDIsIHkyICZsZTsgMTAsMDAwKTxcL3NwYW4+PFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzcyMFx1ZDU1Y1x1ZDU1OFx1YjJlNFx1YmE3NCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzc0IFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWIyZTRcdWJhNzQgNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAyNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJbnRlcnNlY3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gb2Ygc29sdmluZyBhIHNpbXBsZSBnZW9tZXRyeSBwcm9ibGVtIGZvciBmaW5kaW5nIHRoZSBudW1iZXIgb2YgaW50ZXJzZWN0aW9uIHBvaW50cyBvZiB0aGUgYm91bmRhcnkgb2YgYSByZWN0YW5nbGUgYW5kIGEgbGluZSBzZWdtZW50LiBFYWNoIGVkZ2Ugb2YgYSBnaXZlbiByZWN0YW5nbGUgaXMgcGFyYWxsZWwgdG8geC1heGlzIG9yIHktYXhpcy4gKFlvdSBhcmUgdmVyeSBsdWNreSEpIFRoZSBudW1iZXIgb2YgaW50ZXJzZWN0aW9ucyBiZXR3ZWVuIHRoZW0gaXMgemVybywgb25lLCB0d28sIG9yIGluZmluaXR5LiBBIGNhc2Ugb2YgJmxzcXVvO2luZmluaXR5JnJzcXVvOyBvY2N1cnMgaW4gYSBzaXR1YXRpb24gaW4gd2hpY2ggYW4gZWRnZSBvZiB0aGUgcmVjdGFuZ2xlIGFuZCB0aGUgc2VnbWVudCBhcmUgb3ZlcmxhcHBlZCBwYXJ0aWFsbHkgb3Igd2hvbGx5LiBTZWUgdGhlIGZpZ3VyZSBiZWxvdyB3aGljaCBzaG93cyBleGFtcGxlcyBvZiBzZXZlcmFsIHNpdHVhdGlvbnMgYmV0d2VlbiBhIHJlY3RhbmdsZSBhbmQgYSBzZWdtZW50LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvaW50ZXIxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyN3B4OyB3aWR0aDo2MzJweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+KGEpIFNvbWUgZXhhbXBsZXMgb2YgemVybyBpbnRlcnNlY3Rpb24gYmV0d2VlbiBSIGFuZCBsLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvaW50ZXIyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwOXB4OyB3aWR0aDo2MzhweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+KGIpIFNvbWUgZXhhbXBsZXMgb2Ygb25lIGludGVyc2VjdGlvbiBiZXR3ZWVuIFIgYW5kIGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9pbnRlcjMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTExcHg7IHdpZHRoOjY0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4oYykgU29tZSBleGFtcGxlcyBvZiB0d28gaW50ZXJzZWN0aW9ucyBiZXR3ZWVuIFIgYW5kIGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9pbnRlcjQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI0cHg7IHdpZHRoOjYzNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4oZCkgU29tZSBleGFtcGxlcyBvZiBpbmZpbml0ZSBpbnRlcnNlY3Rpb25zIGJldHdlZW4gUiBhbmQgbC4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPkZpZ3VyZSAxLiBFeGFtcGxlcyBvZiBzZXZlcmFsIHNpdHVhdGlvbnMgYmV0d2VlbiBhIHJlY3RhbmdsZSBSKGJsdWUpIGFuZCBhIGxpbmUgc2VnbWVudCBsKHJlZCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGZvdXIgaW50ZWdlcnMgeG1pbiwgeW1pbiwgeG1heCwgYW5kIHltYXggcmVwcmVzZW50aW5nIGEgcmVjcmFuZ2xlIFIsIHdoZXJlICh4bWluLCB5bWluKSBhbmQgKHhtYXgsIHltYXgpIHJlcHJlc2VudCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIGxvd2VyIGxlZnQgY29ybmVyIGFuZCB1cHBlciByaWdodCBjb3JuZXIgb2YgUiwgcmVzcGVjdGl2ZWx5LCAtMTAsMDAwICZsZTsgeG1pbiAmbHQ7IHhtYXggJmxlOyAxMCwwMDAgYW5kIC0xMCwwMDAgJmxlOyB5bWluICZsdDsgeW1heCAmbGU7IDEwLDAwMC4gVGhlIG5leHQgbGluZSBjb250YWlucyBmb3VyIGludGVnZXJzIHgxLCB5MSwgeDIsIGFuZCB5MiByZXByZXNlbnRpbmcgYSBsaW5lIHNlZ21lbnQgbCwgd2hlcmUgKHgxLCB5MSkgYW5kICh4MiwgeTIpIHJlcHJlc2VudCB0aGUgY29vcmRpbmF0ZXMgb2YgdHdvIGVuZCBwb2l1bnRzIG9mIGwsIHJlc3BlY3RpbmVseSwgLTEwLDAwMCAmbGU7IHgxLCB5MSwgeDIsIHkyICZsZTsgMTAsMDAwLCBhbmQgdGhlIGxlbmd0aCBvZiBsIGlzIGdyZWF0ZXIgdGhhbiB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHRoZSBpbnRlcnNlY3Rpb25zIG9mIHRoZSBib3VuZGFyeSBvZiBhIHJlY3RhbmdsZSBhbmQgYSBsaW5lIHNlZ21lbnQgZ2l2ZW4gYnkgaW5wdXQuIElmIHRoZSBudW1iZXIgb2YgdGhlIGludGVyc2VjdGlvbnMgaXMgaW5maW5pdHksIHRoZW4geW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgJnF1b3Q7NCZxdW90OyBpbnN0ZWFkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2014 F번