appa   2년 전

문제의 해법이 다양한 거 같은데, 제 풀이보다 더 좋은 풀이가 있을거란 확신에 토론해보고 싶어서 글을 쓰게 되었습니다!

우선 문제를 풀어보지 않으셨다면 먼저 풀어보는 걸 추천드립니다.

전 일단 직사각형의 성질 2가지를 썼습니다.

1) 직사각형에서의 두 대각선의 길이는 서로 같다.

2) 직사각형에서의 두 대각선은 서로 다른 것을 이등분한다.(두 대각선의 중점이 같다.)

생성 가능한 모든 선분들을 만들어놓고, 길이 순으로(길이가 같다면 선분의 중점 x좌표 순으로) 정렬을 합니다.

그런 다음, 길이가 다르다면 더 이상 볼 필요없고, 선분의 중점 x좌표 또한 달라진다면 더 이상 볼 필요가 없기 때문에 대략 O(n^2 log n)의 시간복잡도를 가지는 것 같습니다.

여러분은 어떻게 푸셨나요?

pl0892029   2년 전

O(N^4) 커팅이 더 빠른 신기한 문제네요. -_-;;

O(N^2 logN)으로 정렬한 후에 O(N^2)으로 정답을 구하는 방법이 가능합니다.

정렬할 때 직선의 기울기까지 고려하여 정렬하면 됩니다.

예전에 썼었던 글이 있으니 한번 보세요 ~_~ 

http://183.106.113.109/showArticle.php?messageid=1...

근데 현실은 (왜인지 모르겠지만) TLE를 수도없이 맞았습니다.

(그림 링크는 이전 더블릿 url이라서 깨져보입니다. ip 주소를 바꿔서 보시면 잘 보입니다.)

appa   2년 전

아하.. 사실 기울기도 고려해볼까 생각했었는데, 중복되는 점의 위치가 없다고 했으므로 2개로만 해도 후보군의 크기가 상수더라구요...

N^2개의 기울기를 계산하면서 생기는 연산의 시간이, 오히려 단순 비교연산을 상수배 더 하는 것보다 더 오래 걸린 것 같습니다.

그런데 그림이 깨져서 실수 연산을 하지 않는 법이 잘 보이지가 않네요ㅠㅠ...

답변 감사합니다!

hujub   2년 전

아직 풀어보지는 않아서 조심스럽지만..

벡터 내적을 이용해서 풀수 있지 않을까요

그러니깐, 우선 각 점들의 차이를 구합니다. 그리고 저장합니다. 여기서 O(N^2) 이 걸리겠네요.

다음, 방금 저장한 것들을 내적합니다. 그리고 0이 되는 것들만 추려내서 저장합니다. 여기서도 아마 O(N^2) 이 걸릴것 같네요.

그럼 이까지 세 점을 구하게 된겁니다. 내적시켰다는건 세점을 이용한거니깐..

다음, 그렇게 0이 된 것들 의 마지막 한 점을 찾아봅니다. 만약 존재한다면 max 로 정답을 업데이트 시켜줍니다.

음 제 생각대로만 된다면 O(N^2 + N^2 + ...) = O(N^2) 정도로 풀릴것 같은데..

음.. 이렇게 하면 구할 수 있지 않을까요? ㅋㅋ 시간나면 한번 풀어봐야겠어요.

appa   2년 전

오.. 벡터 내적은 생각안해봤는데 좋은 아이디어네요! 단지 그 벡터들을 이용해서 하나의 직사각형을 구성할 수 있느냐의 여부도 잘 체크해줘야겠군요!

pichulia   2년 전

모두를 대표해서 누구나 생각할 수 있는 가장 간단한 풀이를 써놓을게요..ㅋㅋㅋ

각 점에 대해서 구하는데, 선택된 점 하나를 중심으로 기울기를 다 구합니다.O(n)

그다음 얘를 각도를 기준으로 정렬해서O(nlogn)

더블포인터로 기울기가 90도가 되도록 i, j를 잡고. O(n)

이 두 점으로 만들어진 네번째 점이 존재하는지 체크합니다.O(1)

이리하면 n*(n+nlogn+n*1) = n^2logn인데...

대각선 길이가 같다는 성질 이용한건 진짜 특이한거같네요ㅋㅋㅋ굳굳

hujub   2년 전

ㅋㅋ백터내적으로 구할려고 했는데  O(n^2) 이 아니라 O(n^3) 이 되버려가지고ㅋㅋ 시간초과가 뜨네요 

여러가지 아이디어들이 많으니깐 참 재밌는 문제네요 

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