[BOJ-JS] 9849번 - Rect

9849번: Rect (acmicpc.net)

 

좌표 평면의 축에 평행한 변을 가진 직사각형이 여럿 주어졌을때, 이 직사각형들의 공통 영역의 넓이를 구하는 문제.

 

아이디어는 다음과 같다.

• 직사각형이 2개 있다면 두 직사각형의 공통 영역을 구하면 된다.
• 3개 있다면 첫 2개의 공통 영역도 직사각형이므로, 이 직사각형과 세 번째 직사각형의 공통 영역을 구하면 된다.
• 4개 있다면 첫 3개의 공통 영역이 직사각형이므로, ...
• 그러니까, n개의 직사각형이 있으면 앞에 있는 직사각형부터 시작해서 공통영역을 계속 찾아나가면 된다.

그렇다면 공통 영역은 어떻게 찾을까?

• 공통 영역의 x좌표 중 작은 값은 첫 번째 직사각형의 최소 x좌표와 두 번째 직사각형의 최소 x좌표 중 큰 값이다.
• 공통 영역의 x좌표 중 큰 값은 첫 번째 직사각형의 최대 x좌표와 두 번째 직사각형의 최대 x좌표 중 작은 값이다.
• y좌표도 비슷한 논리.
• 이때 공통 영역의 x좌표 중 작은 값을 구한 것이 큰 값을 구한 것보다 커질 수가 있다. 이 경우 유효하지 않은 직사각형이 생기므로, 공통 영역이 없다고 볼 수 있다. y값도 마찬가지!

[,...k]=(0+require('fs').readFileSync(0)).split`
`
q=e=0
w=r=1e4
k.map(i=>{
  [a,s,d,f]=i.split` `.map(j=>+j)
  if(s){q=q>a?q:a;w=w<s?w:s;e=e>d?e:d;r=r<f?r:f}
})
console.log((w-q)*(r-e)*+(w>q)*+(r>e))