2.18 PS: 도전

www.acmicpc.net/problem/10098

10098번: 양분

백준 10098 양분.. 아이디어는 대강 생각해 놓았다.진짜 풀어보고 싶다.

 

대충 세 단계 정도면 풀 수 있다. (아마?)

 

1. 합동이면 넓이가 같으므로, 넓이를 이등분하는 x축, y축에 평행한 직선을 이분 탐색으로 빠르게 찾는다.이 "빠르게" 는 x축 기준, y축 기준으로 블록들을 나눈 뒤에 부분합 배열을 만들어서 할 수 있다.

 

2. 교점을 구해서 새로운 다각형 두 개를 만든다. 그 뒤, 도형들을 이루는 벡터를 각각 순서대로 추출한다.

 

3. 합동인지를 판정한다. 합동인 도형은 도형을 이루는 벡터의 순열이 동일하다. 다만 이 순열을 판정하는 것이 상당히 귀찮은데..일단 순환하는 형태이므로 계속 돌려가면서 비교해야 한다는 것과,도형이 거울대칭이거나, 90도의 배수만큼 돌아가 있는 상태도 고려해 줘야 하기 때문이다. 또, 이걸 빠르게 해야 한다. 내 생각에는 KMP 느낌으로 하면 될 것 같다. 벡터는 순환하는 모양새이므로 뒤쪽에 한 바퀴를 더 붙여서 2N-1 길이의 벡터 열을 KMP 돌려서 비교하는 느낌으로...

 

그니까 대충 KMP를 8번 돌려주면 된다. 그리고 위에서 x, y축에 대해서 한번 더 하니까 3번 과정은 대략 16번 돌아간다.

 

그러면 시간복잡도는 1. O(logC) 2. O(logC) or O(1) 3. O(N)인데 상수 큼으로 정리되기까 풀릴 것만 같다.