글 읽기 - 2261번 최근점문제

algospot 8년 전 0

x좌표로 오름차순 정렬 후 분할->점령->;결합 순으로 재귀 알고리즘을 짰는데 시간초과가 뜹니다. 테스트 케이스는 다 만족하는 거 같은데 아무래도 N이 커져 시간초과가 뜨는 것 같은데 재귀함수 없이 구현해야하나요?(stack으로 비재귀판 구현) c언어로 짠 뒤 경과시간과 java로 짠 뒤 경과시간이 엄청 많이 차이나는 것같은데 초보인 저로서는 어디서 얼마만큼의 시간을 잡아먹는 지를 몰라 뭘 고쳐야 시간초 과를 극복할 수 있는지 의문입니다.

import java.util.*;

class point {
	int x,y;
	point(){
		this(0,0);
	}
	point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

class pair {
	int p1,p2;
	pair(){
		this(0,0);
	}
	pair(int p1, int p2){
		this.p1 = p1;
		this.p2 = p2;
	}
}

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		point[] p = new point[N]; 
		for(int i=0;i<N;i++)
			p[i] = new point(sc.nextInt(),sc.nextInt());
		shell_sort(p,N);
		pair pa = new pair();
		pa = closest_points(p,0,N); 
		System.out.println(distance(p[pa.p1],p[pa.p2]));
	
	}
	static int distance(point p1, point p2){
		return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
	}
	static pair closest_points(point[] p, int x1, int x2){
		int i,j;
		int left, right;
		pair pa1 = new pair();
		pair pa2 = new pair();
		pair closest = new pair();
		int d;
		if (x2 - x1 > 3) 
		{
		pa1 = closest_points(p, x1, x1 + (x2-x1)/2);
		pa2 = closest_points(p, x1 + (x2-x1)/2, x2);

		if (distance(p[pa1.p1], p[pa1.p2]) < distance(p[pa2.p1], p[pa2.p2]))
		    closest = pa1;
		else 
		    closest = pa2;
		d = distance(p[closest.p1], p[closest.p2]);

		for (left = x1; p[left].x < p[x1+(x2-x1)/2].x-d-1; left++);
		for (right = x2-1; p[right].x > p[x1+(x2-x1)/2].x+d+1; right--);

		for (i = left; i < right; i++)
		    for (j = i+1; j <= right; j++)
			if (d > distance(p[i], p[j]))
			    {
			    d = distance(p[i], p[j]);
			    closest.p1 = i;
			    closest.p2 = j;
			    }
		return closest;
		}
	    else 
		{
		d = 800000000;
		for (i = x1; i < x2-1; i++)
		    for (j = i+1; j < x2; j++)
			if (d > distance(p[i], p[j]))
			    {
			    d = distance(p[i], p[j]);
			    closest.p1 = i;
			    closest.p2 = j;
			    }
		return closest;
		}
	    }
		
	
	static void shell_sort(point[] p, int n){
		int i,j,k,h;
		point v;
		for(h=n/2;h>0;h/=2)
			for(i=0;i<h;i++)
				for(j=i+h;j<n;j+=h){
					v = p[j];
					k = j;
					while(k>h-1 && p[k-h].x>v.x){
						p[k] = p[k-h];
						k -=h;
					}
					p[k] = v;
				}
	}
	
}

Nada 8년 전 0

59 ~ 69 번째 과정에서 더 시간을 줄일 수 있습니다.
그리고 전체적으로 반복되는 연산이 많이 수행되네요.

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

문제

문제

출처

ICPC

2261번 최근점문제

algospot 8년 전 0

Nada 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말