축사 확장

면접 대비

시간 제한1초메모리 제한128 MB

요약
서로 겹치지 않는 최대 25000개의 축에 나란한 직사각형이 주어질 때, 다른 직사각형과 꼭짓점이나 변에서 닿지 않는 직사각형의 수를 센다.
난이도

보통10점 중 7점

유형
기하, 정렬, 구현
정답자
아직 제출이 없습니다

문제

농부 John의 농장에는 직사각형 축사가 NN개 (1≤N≤250001 \le N \le 25000) 있다. 모든 축사는 각 변이 xx축 또는 yy축과 평행하며, 네 꼭짓점의 좌표는 00 이상 1,000,0001{,}000{,}000 이하의 정수이다. 축사끼리는 내부가 겹치지 않지만, 서로 꼭짓점이나 변을 맞대는 경우는 있을 수 있다.

올해는 우유를 짜야 할 소가 늘어 John은 일부 축사를 넓히고 싶다. 어떤 축사를 확장할 수 있으려면, 그 축사가 다른 어떤 축사와도 꼭짓점이나 변을 공유하지 않아야 한다. 즉, 네 벽을 모두 바깥쪽으로 아주 조금이라도 밀어낼 때 다른 축사에 부딪히지 않아야 한다. 두 축사가 한 점(꼭짓점)에서만 닿아 있어도 두 축사 모두 확장할 수 없다.

확장할 수 있는 축사가 몇 개인지 구하라.

입력

  • 첫째 줄: 정수 NN.
  • 둘째 줄부터 N+1N+1번째 줄까지: 한 축사를 나타내는 정수 네 개 A,B,C,DA, B, C, D (공백으로 구분). 축사의 왼쪽 아래 꼭짓점은 (A,B)(A, B), 오른쪽 위 꼭짓점은 (C,D)(C, D)이며, 0≤A<C≤10000000 \le A < C \le 1000000, 0≤B<D≤10000000 \le B < D \le 1000000을 만족한다.

출력

  • 확장할 수 있는 축사의 개수를 정수 하나로 출력한다.

힌트

예제에서 확장할 수 있는 축사는 입력에 먼저 주어진 두 개뿐이다. 나머지 세 축사는 각각 다른 축사와 꼭짓점 또는 변에서 맞닿아 있어 확장할 수 없다.

예제4

  1. 예제 1

    입력
    5
    0 2 2 7
    3 5 5 8
    4 2 6 4
    6 1 8 6
    0 0 8 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    1
    0 0 1000000 1000000
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2
    0 0 2 2
    2 0 4 2
    
    예상 출력
    0
    
  4. 예제 4

    입력
    2
    0 0 2 2
    2 2 4 4
    
    예상 출력
    0