O(N^4) 커팅이 더 빠른 신기한 문제네요. -_-;;
O(N^2 logN)으로 정렬한 후에 O(N^2)으로 정답을 구하는 방법이 가능합니다.
정렬할 때 직선의 기울기까지 고려하여 정렬하면 됩니다.
예전에 썼었던 글이 있으니 한번 보세요 ~_~
http://183.106.113.109/showArticle.php?messageid=1...
근데 현실은 (왜인지 모르겠지만) TLE를 수도없이 맞았습니다.
(그림 링크는 이전 더블릿 url이라서 깨져보입니다. ip 주소를 바꿔서 보시면 잘 보입니다.)
h0ngjun7 6년 전
문제의 해법이 다양한 거 같은데, 제 풀이보다 더 좋은 풀이가 있을거란 확신에 토론해보고 싶어서 글을 쓰게 되었습니다!
우선 문제를 풀어보지 않으셨다면 먼저 풀어보는 걸 추천드립니다.
전 일단 직사각형의 성질 2가지를 썼습니다.
1) 직사각형에서의 두 대각선의 길이는 서로 같다.
2) 직사각형에서의 두 대각선은 서로 다른 것을 이등분한다.(두 대각선의 중점이 같다.)
생성 가능한 모든 선분들을 만들어놓고, 길이 순으로(길이가 같다면 선분의 중점 x좌표 순으로) 정렬을 합니다.
그런 다음, 길이가 다르다면 더 이상 볼 필요없고, 선분의 중점 x좌표 또한 달라진다면 더 이상 볼 필요가 없기 때문에 대략 O(n^2 log n)의 시간복잡도를 가지는 것 같습니다.
여러분은 어떻게 푸셨나요?