yuchan0629   5년 전

일반적으로 하는 이차배열로 하지 않고 수학적인 알고리즘으로 구현했는데 틀렸습니다가 뜨네요. 어디가 틀린건지 알려주시거나 반례를 찾아주시면 감사하겠습니다!^^

gaelim   5년 전

input :

3

0 0

1 1

2 2

ans : 138

종이 2쌍간 겹치는 영역을 모두 탐색해서 영역 넓이를 빼주시는데 

이미 겹친다고 판단해서 빼준 영역에 대해 또 빼주는 경우가 생깁니다. 

틀린예 )
(1,2) 겹침영역 : 81  
(1,3)겹침영역 : 64
(2,3) 겹침영역 : 81
= 226 
300 - 226 = 74 

맞은예 )
(1,2) 겹침영역 : 두 종이에서 81 
(1,3) 겹침영역 : 3 종이에서만 64 ( 1 종이 영역은 앞서 (1,2) 계산할때 차감됨) 
(2,3) 겹침영역 : 두 종이에서 17 ( 2 종이 영역은 앞서 (1,2) 계산할 때 차감됨, 3 종이 영역은 앞서 (1, 3) 계산할 때 차감됨)
= 162
300 - 162 = 138

댓글을 작성하려면 로그인해야 합니다.