백준 2261 가장 가까운 두 점 찾기

#include <iostream>
#include <algorithm>

using namespace std;

int n;

struct dot {
	int x;
	int y;
	bool operator>(dot rdot) {
		return this->y > rdot.y;
	}
	bool operator<(dot rdot) {
		return this->y < rdot.y;
	}
};

dot dotArr[100001];

int dist(int AIndex, int BIndex) {
	return (dotArr[BIndex].x - dotArr[AIndex].x) * (dotArr[BIndex].x - dotArr[AIndex].x) + (dotArr[BIndex].y - dotArr[AIndex].y) * (dotArr[BIndex].y - dotArr[AIndex].y);
}
int calc(int startIndex, int endIndex) {
	if (endIndex - startIndex == 1) {
		return dist(startIndex, endIndex);
	}
	else if (endIndex - startIndex == 2) {
		return min(min(dist(startIndex, startIndex + 1), dist(startIndex + 1, startIndex + 2)), dist(startIndex, endIndex));
	}
	int midIndex = (int)((startIndex + endIndex) / 2);
	int leftMin = calc(startIndex, midIndex);
	int rightMin = calc(midIndex + 1 , endIndex);

	int lessDist = min(leftMin, rightMin);
	int midY = dotArr[midIndex].y;

	int leftPartition, rightPartition;
	for (leftPartition = midIndex; leftPartition >= startIndex; leftPartition--) {
		if (midY - dotArr[leftPartition].y < lessDist) {
			for (rightPartition = midIndex + 1; rightPartition <= endIndex; rightPartition++) {
				if (dotArr[rightPartition].y - midY < lessDist) {
					lessDist = min(lessDist, dist(leftPartition, rightPartition));
				}
				else {
					break;
				}
			}
		}
		else {
			break;
		}
	}
	return lessDist;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &dotArr[i].x, &dotArr[i].y);
	}
	sort(dotArr, dotArr + n);
	int result = calc(0, n - 1);
	cout << result << endl;
}

처음 풀었던 코드

분할 정복 문제를 분할 정복으로 풀었더니 시간초과가 뜨더라

nlog(n)인데 왜일까.. 고민하다

이것저것 해도 계속 시간초과길레 

백준님께서 올리신 풀이를 참고했다.

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int n;

struct Point {
	int x, y;
	Point() {}
	Point(int x, int y) : x(x), y(y) {}
	bool operator > (const Point& other) const {
		if (this->y == other.y) {
			return this->x > other.x;
		}
		return this->y > other.y;
	}
	bool operator < (const Point& other) const {
		if (this->y == other.y) {
			return this->x < other.x;
		}
		return this->y < other.y;
	}
};

bool cmpX(const Point &left, const Point& right) {
	return left.x < right.x;
}

int dist(const Point& start, const Point& end) {
	return (start.x - end.x)*(start.x - end.x) + (start.y - end.y)*(start.y - end.y);
}

int main() {
	scanf("%d", &n);
	vector<Point> pointVector(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &pointVector[i].x, &pointVector[i].y);
	}
	sort(pointVector.begin(), pointVector.end(), cmpX);
	int minDist = dist(pointVector[0], pointVector[1]);
	set<Point> candidate = { pointVector[0], pointVector[1] };

	int distOverIndex = 0;
	for (int i = 2; i < n; i++) {
		Point& nowPoint = pointVector[i];
		while (distOverIndex < i) {
			Point& p = pointVector[distOverIndex];
			int xDist = nowPoint.x - pointVector[distOverIndex].x;
			if (xDist * xDist > minDist) {
				candidate.erase(p);
				distOverIndex++;
			}
			else {
				break;
			}
		}
		int sqrtDist = (int)sqrt((double)minDist) + 1;
		Point lowerPoint = Point(-100000, nowPoint.y - sqrtDist);
		Point upperPoint = Point(100000, nowPoint.y + sqrtDist);
		auto lower = candidate.lower_bound(lowerPoint);
		auto upper = candidate.upper_bound(upperPoint);
		for (auto it = lower; it != upper; it++) {
			int newDist = dist(nowPoint, *it);
			if (newDist < minDist) minDist = newDist;
		}
		candidate.insert(nowPoint);
	}

	printf("%d", minDist);
	return 0;
	
}

정답~

i=[2..n]에 대하여,

Point가 든 vector(이하 vector)를 순회하면서

거리를 계산할 가치가 있는 점들이 있는 set(이하 candidate)중 점 하나(Point)를 골라서 vector[i] 사이의 x좌표만의 거리를 비교하여

그 거리가 현재까지 구한 최소 거리(이하 minDist)보다 크면 candidate에서 그 Point를 지운다.

vector는 처음부터 x좌표에 대해 정렬이 되어 있는 상태이므로, x좌표가 minDist보다 작은 경우가 나오면

그 상황의 Index를 distOverIndex에 저장한다.

그 후, candidate set을 y좌표에 따라 정렬한 뒤, 

upper_bound와 lower_bound를 이용하여 candidate에 있는 좌표와 vector[i]와의 y 좌표가 minDist보다 작은 경우만을 간추려

각각의 경우에 대하여 dist를 계산하고 minDist를 갱신한다.

마지막으로 candidate에 vector[i]를 insert()한 뒤, i++을 수행.

set는 distOverIndex덕분에 순회를 반복하지 않고 한번만 수행하므로 수행시간에 영향을 주지 않는다.

그리고 candidate는 set이기 때문에 upper_bound, lower_bound를 log(n)시간 안에 찾고, set에 insert()할때도 log(n)시간에 정렬하여 들어온다.

결론적으로 정렬을 수행하는 nlog(n)이 가장 긴 시간이 되기 때문에 nlog(n)이 수행 시간이 됨.