lyzqm   6년 전

우선 두 점을 잡아서 그 선분과 정사각형을 이룰 수 있는 네 점을 구합니다.

그 점들이 set에 저장되있는지 확인해서 최대크기 정사각형을 구하는 방법인데요

O(N^2 log(N))으로 풀었는데 시간초과가 나네요

시간을 줄일 수 있는 방법이 있을까요? 생각이 떠오르질 않네요


wjdclgns12   6년 전

잡은 두 점의 선분의 길이가 지금까지 찾은 최대크기 정사각형의 한 변의 길이보다 짧으면 스킵하면 되지않을까요?

lyzqm   6년 전

똑같이 시간초과네요 

두 점의 선분을 저장한 뒤에 길이를 기준으로 내림차순으로 정렬한 후에 

정사각형을 찾으면 탈출하는 방식도 해봤는데 이것도 마찬가집니다 ㅠㅠ

최악의 입력이 들어오면 결국 연산해야하니까 그런거 같아요

lyzqm   6년 전

검사를 한번만하니까 통과되네요

chogahui05   6년 전

전 set 대신에 unordered_map 써서 해결은 했는데요.

크기가 커서 아슬아슬하게 통과한 기억이 나네요.. 개인적으로 지뢰보단.. 뭐..

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