글 읽기 - 기하문제에서의 시간초과

strake32 3년 전 0

안녕하세요

문제 1221 세 점 사이의 거리를 풀다가 질문드립니다.

점과 점 사이 라인의 수가 많아지면서 타임아웃이 발생했습니다.

첨엔 모든점을 저장했다가 메모리초과가 떴는데, 산너머 산이군요..ㅎㅎ;

이러한 기하문제에서 모든 라인의 경우를 검사하지 않고 어떻게 해야 효율적으로 연산할 수 있나요??

아니면 해당 문제를 해결하기 위해 참고할만한 알고리즘이나 정해 풀이법이 있으면 알려주시면 감사하겠습니다.

코드를 같이 첨부하겠습니다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define EPSILON 0.000001
struct dot_data {
	int x, y, z;
};

double getDist_3dm(dot_data a, dot_data b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
bool compareDouble(double a, double b) {
	double result = fabs(a - b);
	return result < EPSILON ? 1 : 0;
}
vector <dot_data> v;
vector <double> length_v;
double min_length;
int main() {
	dot_data tmp;
	int N, result = 1, idx = 1;
	double line_length;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp.x >> tmp.y >> tmp.z;
		v.push_back(tmp);
	}

	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			line_length = getDist_3dm(v[i], v[j]);
			if (i == 0 && j == 1)
				min_length = line_length;

			else if (compareDouble(line_length, min_length) ||
				line_length < min_length){
				min_length = line_length;
				length_v.push_back(line_length);
			}
		}
	}
	sort(length_v.begin(), length_v.end());

	cout << pow(min_length, 2) << endl;
	if (length_v.size() != 0){
		while (compareDouble(min_length, length_v[idx++])) {
			result++;
		}
	}
	cout << result << endl;
	return 0;
}

scvhero 3년 전 0

https://www.acmicpc.net/problem/2261

2차원 버전 문제입니다

이 문제부터 풀어보시는게 좋을 것 같네요

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

문제

문제

출처

ICPC

기하문제에서의 시간초과

strake32 3년 전 0

scvhero 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말