글 읽기 - (10시간넘게 못찾고 있습니다 ㅠㅠ) 시간초과

gs25 2년 전 1

x축으로 정렬 후 반으로 나누는 일반적인 분할 정복으로 풀었습니다.
https://casterian.net/archives/92 풀이를 보고 풀었습니다. 그러나 제가 생각하는 코드의 시간복잡도는 n log n 인데 시간초과가 납니다. 중간에 잘못된 부분이 있을텐데 몇시간을 찾아봐도 모르겠습니다. t1, t2, t3, t4, t5를 넣어보니 t2에서 t1 사이만 시간이 오래 걸렸습니다. 마스터 정리를 생각해보면 참 납득이 안되는 결과입니다. 정말 10시간 넘게 본 것 같은데 정말 모르겠습니다 ㅠㅠㅠ 한번만 봐주시면 정말 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

int n;             // 전체 점 개수

typedef pair<int, int> pii;
typedef pair<int, int> Point;

bool comp(const pii& a, const pii& b)
{
	return a.first < b.first;
}

clock_t t1, t2, t3, t4, t5;


Point v[100010];

int dist(Point& p1, Point& p2) {
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

bool cmp(Point& p1, Point& p2) {
	return (p1.x == p2.x) ? p1.y < p2.y : p1.x < p2.x;              // x값으로 정렬
}

bool cmp2(Point& p1, Point& p2) {
	return (p1.y == p2.y) ? p1.x < p2.x : p1.y < p2.y;              // y값으로 정렬
}

int smallest(int s, int e) {
	t1 = clock();
	if (e == s + 2) {
		return dist(v[s], v[s + 1]);
	}
	if (e == s + 3) {
		return min({ dist(v[s], v[s + 1]), dist(v[s + 1], v[s + 2]), dist(v[s + 2], v[s]) });
	}

	int m = (s + e) / 2;
	int d1 = smallest(s, m);
	int d2 = smallest(m, e);

	int d = min(d1, d2);

	int line = (v[m - 1].x + v[m].x) / 2;

	Point middle[100010] = {};
	int middlesize = 0;

	t2 = clock();

	/*
	for (int i = s; i < e; i++) {
		if ((v[i].x - line) * (v[i].x - line) < d) middle[middlesize++] = v[i];
	}*/

	auto lo_it = lower_bound(v + s, v + e, pii(line - (int)sqrt(d) - 1, 0), comp) - v;
	auto up_it = upper_bound(v + s, v + e, pii(line + (int)sqrt(d) + 1, 0), comp) - v;

	for (int i = max(lo_it, s); i < min(up_it, e); i++) {
		middle[middlesize++] = v[i];
	}

	t3 = clock();

	sort(middle, middle + middlesize, cmp2);

	t4 = clock();

	int cnt = 0;

	for (int i = 0; i < middlesize; i++) {
		for (int j = i + 1; j < middlesize && (middle[i].y - middle[j].y) * (middle[i].y - middle[j].y) < d; j++) {
			d = min(d, dist(middle[i], middle[j]));
			cnt++;                                        // 최대 7*n
		}
	}

	t5 = clock();

	//if(s==0&&e==n) cout << cnt << "\n";
	//if (s == 0 && e == n) cout << t2 - t1 << " " << t3 - t2 << " " << t4 - t3 << " " << t5 - t4 << "\n";
	return d;
}

int main(void) {

	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[i] = { x,y };
	}
	sort(v, v + n, cmp);
	for (int i = 0; i < n - 1; i++) {
		if (v[i].x == v[i + 1].x && v[i].y == v[i + 1].y) {
			cout << "0"; return 0;
		}
	}
	cout << smallest(0, n) << "\n";
}

Green55 2년 전 2

1. Point middle[100010] 를 함수 내에 잡으면 매번 메모리를 새로 잡아야하므로 오래 걸립니다.

2. clock()도 오래 걸립니다.

gs25 2년 전 0

제 생명의 은인이에요

gs25 2년 전 0

단순 배열잡는게 그렇게 오래걸릴 줄 몰랐네요. ㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

(10시간넘게 못찾고 있습니다 ㅠㅠ) 시간초과

gs25 2년 전 1

Green55 2년 전 2

gs25 2년 전 0

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말