글 읽기 - 2261번 시간초과/틀렸습니다 질문드립니다.

yoonhagi 3년 전 0

해보다해보다 안돼서 이 질문 게시판에 있는 (거짓말 안하고) 모든 글들과 구글링 등을 사용했는데도 안돼서 질문 올려봅니다.

처음으로 질문 올려서 좀 두서가 없을 수도 있겠네요.

아래의 코드는 해보다 해보다 C++로 하신 분이 질문게시판에 올리고 해결되었다는 코드를 제가 C언어 식으로 변환해서 그대로 타이핑해본 코드입니다. (출처 : https://www.acmicpc.net/board/...)

(저는 C++에 대한 지식이 없어서 그냥 보고 들은 것을 바탕으로 감으로 그냥 변환해봤네요 ㅎㅎ...)

이랬는데도 11%에서 시간초과 걸려서 정말 당황스럽네요.

그분의 코드와 저의 코드가 다른 점은 sorting 밖에는 없는 것 같은데,

혹시 제 qsort를 위한 compare 함수에 무슨 문제가 있는건지(아무리 생각해도 없는것같은데..),

아니면 뭔가 새로운 문제가 제 코드에 있는것인지 모르겠습니다.

지식인 분들의 도움이 절실합니다ㅠㅠ

#include <stdio.h>
#include <stdlib.h>
typedef struct point{
	int x, y;
} P;
P p[100001];
int dist(P a, P b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int compare(const void *a, const void *b){
	if(((P *) a)->x > ((P *) b)->x)
		return 1;
	else if(((P *) a)->x < ((P *) b)->x)
		return -1;
	else{
		if(((P *) a)->y > ((P *) b)->y)
			return 1;
		else if(((P *) a)->y < ((P *) b)->y)
			return -1;
		else
			return 0;
	}
}

int ans(int start, int end){
	if(start == end)
		return 0;
	if(end - start == 1)
		return dist(p[start], p[end]);
	
	int mid = (start + end) / 2;
	int a, m = dist(p[start], p[end]);

	if(start != mid){
		if(m > (a = ans(start, mid)))
			m = a;
	}
	if(end != mid + 1){
		if(m > (a = ans(mid + 1, end)))
			m = a;
	}

	int i, j;
	for(i=mid; i>=start; i--){		//left part
		for(j=mid+1; j<=end; j++){	//right part
			a = p[j].x - p[i].x;
			if(a * a >= m)
				break;
			else{
				a = dist(p[i], p[j]);
				if(m > a)
					m = a;
			}
		}
		if(j == mid + 1)
			break;
	}

	return m;
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d %d", &p[i].x, &p[i].y);
	qsort(p, n, sizeof(P), compare);
	
	printf("%d", ans(0, n-1));
}

ha_ram 3년 전 0

입력으로 들어온 점들의 x값이 모두 같다면

44번~57번 for문을 돌 때 시간초과가 날것같네요.

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