축사 확장
면접 대비시간 제한1초메모리 제한128 MB
서로 겹치지 않는 최대 25000개의 축에 나란한 직사각형이 주어질 때, 다른 직사각형과 꼭짓점이나 변에서 닿지 않는 직사각형의 수를 센다.
문제
농부 John의 농장에는 직사각형 축사가 개 () 있다. 모든 축사는 각 변이 축 또는 축과 평행하며, 네 꼭짓점의 좌표는 이상 이하의 정수이다. 축사끼리는 내부가 겹치지 않지만, 서로 꼭짓점이나 변을 맞대는 경우는 있을 수 있다.
올해는 우유를 짜야 할 소가 늘어 John은 일부 축사를 넓히고 싶다. 어떤 축사를 확장할 수 있으려면, 그 축사가 다른 어떤 축사와도 꼭짓점이나 변을 공유하지 않아야 한다. 즉, 네 벽을 모두 바깥쪽으로 아주 조금이라도 밀어낼 때 다른 축사에 부딪히지 않아야 한다. 두 축사가 한 점(꼭짓점)에서만 닿아 있어도 두 축사 모두 확장할 수 없다.
확장할 수 있는 축사가 몇 개인지 구하라.
입력
- 첫째 줄: 정수 .
- 둘째 줄부터 번째 줄까지: 한 축사를 나타내는 정수 네 개 (공백으로 구분). 축사의 왼쪽 아래 꼭짓점은 , 오른쪽 위 꼭짓점은 이며, , 을 만족한다.
출력
- 확장할 수 있는 축사의 개수를 정수 하나로 출력한다.
힌트
예제에서 확장할 수 있는 축사는 입력에 먼저 주어진 두 개뿐이다. 나머지 세 축사는 각각 다른 축사와 꼭짓점 또는 변에서 맞닿아 있어 확장할 수 없다.