글 읽기 - 2261 시간초과에 대하여

baesin92 7년 전 0

계속 시간초과가 뜨는데 어느부분에서 시간을 줄여야 할까요...?

몇번을 하면서 realloc을 malloc으로 바꾸고 3항연산자 사용 줄이고 하는데도 계속 떠서 힘드네요 ㅠㅠ

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<float.h>
#include<string.h>

typedef struct point{
	float x;
	float y;
} point;

float closestPair(point * p,int size);
float distance(point p1,point p2);

int compareX (const void* a, const void* b){
	return ((point *)a)->x - ((point *)b)->x;
}
int compareY (const void* a, const void* b){
	return ((point *)a)->y - ((point *)b)->y;
}
int main(){
	float x,y,result;
	point *points=NULL;
	int size=0;
	int i;
    scanf("%d",&i);
	points = (point *)malloc(sizeof(point)*i);
	while(size<i){
        scanf("%f %f",&x,&y);
		points[size].x = x;
		points[size].y = y;
		size++;
	}
	qsort(points,size,sizeof(point),compareX);
	result= closestPair(points,size);
	printf("%f\n",result);
    return 0;
}
float distance(point p1,point p2){
	return pow((p1.x-p2.x) , 2)+pow((p1.y-p2.y) , 2);
}
float closestPair(point * p,int size){
	int mid,newsize=0,i,j;
	float preResult, postResult,midX,shortest=FLT_MAX;
	point* pre;
	point* post;
	point* between=NULL;
	if(size <= 3) {
		for(i=0;i<size;i++){
			for(j=i+1;j<size;j++){
				float temp = distance(p[i],p[j]);
				if(temp<shortest)
					shortest = temp;
			}
		}
		return shortest;
	}
	mid = size/2;
	pre = (point *)malloc(sizeof(point)*mid);
	post = (point *)malloc(sizeof(point)*(size-mid));
	memcpy(pre,p,mid*sizeof(point));
	memcpy(post,p+mid,(size-mid)*sizeof(point));
	preResult = closestPair(pre,mid);
	postResult = closestPair(post,size-mid);
	midX = (p[mid-1].x+p[mid].x)/2;
	shortest = preResult>postResult ? postResult : preResult;
	between = (point *)malloc(sizeof(point)*size);
	for(i=0;i<size;i++){
		if(p[i].x<midX+shortest && p[i].x>midX-shortest){
			between[newsize].x = p[i].x;
			between[newsize].y = p[i].y;
			newsize++;
		}
	}
	qsort(between,newsize,sizeof(point),compareY);
	for(i=0;i<newsize;i++){
		for(j=i+1;j<newsize && between[j].y-between[i].y<shortest;j++){
			float temp = distance(between[i],between[j]);
			if(temp<shortest)
				shortest = temp;
		}
	}
	return shortest;
}

bupjae 7년 전 0

이 문제는 실수 연산 없이 정수 연산만으로 풀 수 있습니다. 굳이 두 점 사이의 거리의 "제곱"을 구하라고 명시한 것도 그 때문입니다.

bupjae 7년 전 0

몇가지 더 첨언을 하자면

# pre 배열과 post 배열을 정말로 꼭 복사해서 써야만 할까요?

# 배열을 동적 할당해 놓고 쓰레기 안 치우는 건 정말정말 추천하고 싶지 않습니다. 쓰레기 치우는 데 걸리는 시간보다 어질러진 방에 추가로 배열을 위한 메모리 공간을 찾아내는 데 더 시간이 걸릴 수도 있습니다.

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

문제

문제

출처

ICPC

2261 시간초과에 대하여

baesin92 7년 전 0

bupjae 7년 전 0

bupjae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말