글 읽기 - 93퍼에서 자꾸 시간초과

ckdgus2482 8년 전 0

x에 대해서 정렬한 다음, 이분해서 해결하는 분할정복 알고리즘입니다.

좌측 부분문제와 우측 부분문제에서 구한 답을 비교하여 더 작은걸 minimum에 넣었습니다.

mlsIter는 분할된 좌측 부분에서 그것의 x좌표와 분할한 경계점의 x좌표 거리가 minimum 미만인 점들 중 x좌표가 가장 작은 점을 가리킵니다.

mreIter는 분할된 우측 부분에서 그것의 x좌표와 분할한 경계점의 x좌표 거리가 minimum 미만인 점들 중 x좌표가 가장 큰 점을 가리킵니다.

그상태에서 mlsIter부터 분할한 경계점 미만의 점들과 분할한 경계점부터 mreIter 미만의 점들과 1:1로 거리를 비교해서 가장 작은 거리를 찾고 이것과 minimum을 비교해서 더 작은 값을 리턴하도록 했습니다.

거리계산을 중복으로 하는 좌표쌍은 없는데 채점 93퍼쯤 가서 시간초과가 나네요.

알고리즘의 개선점이 있을까요? 아니면 코드수준에서의 최적화를 고려해야할까요?

#include <iostream>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;
int main() {
	int n, x, y;
	multimap<int, int> mm;
	scanf("%d", &n);
	for (int i = 0; i != n; ++i) {
		scanf("%d%d", &x, &y);
		mm.insert({ x,y });
	}
	function<int(multimap<int, int>::const_iterator, multimap<int, int>::const_iterator)> f = [&f](multimap<int, int>::const_iterator begin, multimap<int, int>::const_iterator end) {
		int dist = distance(begin, end);
		if (dist == 1) return 987654321;
		if (dist == 2) {
			auto iter = next(begin, 1);
			int dx = iter->first - begin->first;
			int dy = iter->second - begin->second;
			return dx*dx + dy*dy;
		}
		multimap<int, int>::const_iterator mIter = next(begin, dist / 2);
		int lx = f(begin, mIter), rx = f(mIter, end);
		int minimum = min(lx, rx);
		multimap<int, int>::const_iterator mlsIter = mIter;
		while (distance(begin, mlsIter) > 0 && (mIter->first - mlsIter->first)*(mIter->first - mlsIter->first) < minimum)
			--mlsIter;
		if(begin != mlsIter)
			++mlsIter;
		multimap<int, int>::const_iterator mreIter = mIter;
		while (distance(mreIter, end) > 0 && (mreIter->first - mIter->first)*(mreIter->first - mIter->first) < minimum)
			++mreIter;
		int mMin = 987654321;
		for (multimap<int, int>::const_iterator lIter = mlsIter; lIter != mIter; ++lIter) {
			for (multimap<int, int>::const_iterator rIter = mIter; rIter != mreIter; ++rIter) {
				int dx = rIter->first - lIter->first;
				int dy = rIter->second - lIter->second;
				int dis = dx*dx + dy*dy;
				mMin = dis < mMin ? dis : mMin;
			}
		}
		return (mMin < minimum ? mMin : minimum);
	};
	printf("%d", f(mm.begin(), mm.end()));
}

ntopia 8년 전 1

x좌표만 신경쓰면

점들의 x좌표가 모두 같고 y좌표만 다른 경우에는

시간복잡도가 O(n^2) 이 되는 것 같습니다

h0ngjun7 7년 전 0

게다가 멀티맵이라서 많이 느린 것 같습니다. 저도 x좌표 같은 게 많은 경우 TLE나야하는데 300ms로 통과했거든요....

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