만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

축사 확장

면접 대비

시간 제한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