글 읽기 - 자바 시간 초과가 발생합니다. (11%)

kkanggu 2년 전 0

Line Sweeping 방식으로 접근을 하였습니다.

x축의 값에 따라, 그리고 같은 값이라면 y축의 값에 따라 배열을 정렬합니다.

이후 각 점을 기준으로 x축이나 y축 값이 sqrt(min-1) 내부에 있는 점끼리 비교를 하여 min 값을 갱신하는 방식입니다.

10%에서 오래 걸리다가 11%로 넘어간 직후 시간 초과가 발생합니다.

어떠한 부분에서 문제가 생기는지 잘 모르겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;



public class OJ_2261_TheClosestDots
{
	public static void main ( String [] args ) throws IOException
	{
		BufferedReader br = new BufferedReader ( new InputStreamReader ( System.in ) ) ;
		int iMin = Integer.MAX_VALUE ;
		int iCnt = Integer.parseInt ( br.readLine () ) ;
		int irgDot [] [] = new int [ iCnt ] [ 2 ] ;
		int iRightBound ;
		int iUpperBound ;
		int iLowerBound ;
		int j ;
		
		
		
		for ( int i = 0 ; i < iCnt ; ++i )
		{
			irgDot [ i ] = Arrays.stream ( br.readLine ().split ( " " ) ).mapToInt ( Integer :: parseInt ).toArray () ;
		}
		
		Arrays.sort ( irgDot , new Comparator < int[] > ()
				{
					@Override
					public int compare ( int[] o1 , int[] o2 )
					{
						if ( o1 [ 0 ] == o2 [ 0 ] )
						{
							return o1 [ 1 ] - o2 [ 1 ] ;
						}
						else
						{
							return o1 [ 0 ] - o2 [ 0 ] ;
						}
					}
				} ) ;
		
		iMin = iGetDistance ( irgDot [ 0 ] [ 0 ] , irgDot [ 0 ] [ 1 ] , irgDot [ 1 ] [ 0 ] , irgDot [ 1 ] [ 1 ] ) ;
		
		
		for ( int i = 0 ; i < iCnt - 1 ; ++i )
		{
			iRightBound = ( int ) ( irgDot [ i ] [ 0 ] + Math.sqrt ( iMin - 1 ) ) ;
			iLowerBound = ( int ) ( irgDot [ i ] [ 1 ] - Math.sqrt ( iMin - 1 ) ) ;
			iUpperBound = ( int ) ( irgDot [ i ] [ 1 ] + Math.sqrt ( iMin - 1 ) ) ;
			j = i + 1 ;
			
			if ( j == iCnt )
			{
				System.out.println ( iMin ) ;
				System.exit ( 0 ) ;
			}
			
			while ( irgDot [ j ] [ 0 ] <= iRightBound )
			{
				if ( ( irgDot [ j ] [ 1 ] >= iLowerBound ) && ( irgDot [ j ] [ 1 ] <= iUpperBound ) )
				{
					iMin = Math.min ( iMin , iGetDistance ( irgDot [ i ] [ 0 ] , irgDot [ i ] [ 1 ] , irgDot [ j ] [ 0 ] , irgDot [ j ] [ 1 ] ) ) ;
					
					if ( 0 == iMin )
					{
						System.out.println ( 0 ) ;
						System.exit ( 0 ) ;
					}
					
					iRightBound = ( int ) ( irgDot [ i ] [ 0 ] + Math.sqrt ( iMin - 1 ) ) ;
					iLowerBound = ( int ) ( irgDot [ i ] [ 1 ] - Math.sqrt ( iMin - 1 ) ) ;
					iUpperBound = ( int ) ( irgDot [ i ] [ 1 ] + Math.sqrt ( iMin - 1 ) ) ;
					
					++j ;
				}
				else
				{
					while ( ( irgDot [ j ] [ 1 ] > iUpperBound ) || ( irgDot [ j ] [ 1 ] < iLowerBound ) )
					{
						++j ;
						
						if ( j == iCnt )
						{
							break ;
						}
					}
				}
				
				if ( j == iCnt )
				{
					break ;
				}
			}
		}
		
		System.out.println ( iMin ) ;
	}
	
	private static int iGetDistance ( int iX1 , int iY1 , int iX2 , int iY2 )
	{
		return ( ( iX1 - iX2 ) * ( iX1 - iX2 ) + ( iY1 - iY2 ) * ( iY1 - iY2 ) ) ;
	}
}

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

문제

문제

출처

ICPC

자바 시간 초과가 발생합니다. (11%)

kkanggu 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말