dla123kr   7년 전

안녕하세요. 시간초과가 왜 뜨는지 잘 모르겠습니다..


해싱을 위해 map을 사용하여 해당 좌표가 존재하는지 표현했습니다.

vector에 값을 다 담아 O(N2) 만큼 반복문 돌리면 될 줄 알았는데 안되네요.


어디가 문제일까요 ??

bupjae   7년 전

입력으로 주어지는 점이 모두 정수 좌표인데 굳이 double 을 써야 하나요?

dla123kr   7년 전

@bupjae 두 개의 점을 골랐을 때 중앙에 점이 있는지 확인하기 위해 double로 했습니다.

두 점의 차이가 홀수면 정확하게 안될 거 같아서요.

bupjae   7년 전

예를 들어 +1, +2 두 점을 골랐을 때 두 점 사이의 점은 +1.5 가 되는데

애당초 입력으로 +1.5 란 점은 절대로 들어오지 않을테니 +1.5 라는 걸 계산할 필요도 없이 다음으로 넘어가도 되지 않을까요?

dla123kr   7년 전

@bupaje 답글 감사합니다.

말씀을 들어보고 차이가 홀수인 경우는 건너 뛰었는데도 타임리밋이네요 ㅜ

bupjae   7년 전

이 프로그램에서는 서로 다른 두 가지 입력 방법 (cin, scanf) 를 쓰고 있습니다.

100% 확실하진 않지만 이게 성능에 영향을 미칠 가능성이 있을 수 있습니다.


기왕 scanf 를 쓰게 된 거, 모든 입출력을 scanf 및 printf 로 통일한 뒤 시도해 보세요

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