글 읽기 - 고속도로 10254 답이 없어요...

wagurano 4년 전 0

50%에서 타임아웃이 났습니다.

방법은 convex hull로 볼록껍질 스택에 쌓은다음

스택에 쌓여진 점들을 2중 for문으로 돌렸는데 타임아웃나네요

혹시나해서 백준님 풀이소스 고대로 제출해봤는데도 타임오바 납니다. 뭐가문제일까요..ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q10254 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i = 0 ; i < T ; i++){
			
			int N = Integer.parseInt(br.readLine());
			Point[] input = new Point[N];
			
			for(int j = 0 ; j < N ; j++){
				StringTokenizer token = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(token.nextToken());
				int y = Integer.parseInt(token.nextToken());
				Point tmp = new Point(x, y);
				input[j] = tmp;
			}
			
			//최하위 point를 찾는다
			Point st = input[0];
			for(int j = 0 ; j < N ; j++){
				if(input[j].y < st.y ||(input[j].x < st.x && input[j].y == st.y)){
					st = input[j];
				}
			}
			final Point sp = st;

			//최하위 point기준으로 기울기별 array를 정렬
			Arrays.sort(input, new Comparator<Point>() {
				/**
				 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
				 */
				@Override
				public int compare(Point a, Point b) {
					long ccw = ccw(sp, a, b);
					if(ccw > 0){
						return 1;
					}else if(ccw < 0){
						return -1;
					}else{
						double dist1 = dist(sp, a);
						double dist2 = dist(sp, b);
						if(dist1 > dist2){
							return 1;
						}else if(dist1 < dist2){
							return -1;
						}else{
							return 0;
						}
					}
				}
			});
			
			//정렬된 기준으로 stack에 쌓는다
			Stack stack = new Stack<>();
			for(int j = 0 ; j < N ; j++){
				int size = stack.size();
				//볼록이 아닌케이스(시계방향이 존재시)
				while(size >= 2 && ccw((Point)stack.get(size-2), (Point)stack.get(size-1), input[j])>=0){
					stack.pop();
					size = size-1;
				}
				//넣는다.
				stack.push(input[j]);
			}	

			
			Point a = sp;
			Point b = sp;
			long dist = dist(a , b);
			for(int j = 0 ; j < stack.size() ; j++){
				for(int k = j ; k < stack.size() ; k++){
					if(dist < dist((Point)stack.get(j), (Point)stack.get(k))){
						dist = dist((Point)stack.get(j), (Point)stack.get(k));
						a = (Point)stack.get(j);
						b = (Point)stack.get(k);
					}
				}
			}
			System.out.println(a.x+" "+a.y+" "+b.x+" "+b.y);
			
			/*
            int x = 0, y = 0;
            long ans = 0;
            int k = 0;
            for (int j=0; j<stack.size(); j++) {
                while (dist((Point)stack.get(j), (Point)stack.get(k)) < dist((Point)stack.get(j), (Point)stack.get((k+1)%stack.size()))) {
                    k = (k+1)%stack.size();
                }
                long d = dist((Point)stack.get(j), (Point)stack.get(k));
                if (ans < d) {
                    ans = d;
                    x = j;
                    y = k;
                }
            }
			
            Point a = (Point)stack.get(x);
            Point b = (Point)stack.get(y);
            System.out.println(a.x+" "+a.y+" "+b.x+" "+b.y);
			*/
		}
	}

	/**
	 * @param sp
	 * @param a
	 * @return
	 */
	protected static long dist(Point sp, Point a) {
		long dist = (long)(sp.x - a.x)*(sp.x - a.x)+(long)(sp.y - a.y)*(sp.y - a.y);
		return dist;
	}

	/**
	 * @param st
	 * @param a
	 * @param b
	 * @return
	 */
	protected static long ccw(Point sp, Point a, Point b) {
		long ccw = (long)((long)sp.x*a.y+(long)a.x*b.y+(long)b.x*sp.y)-(long)((long)a.x*sp.y+(long)b.x*a.y+(long)sp.x*b.y);
		return ccw;
	}

}

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

kyo20111 4년 전 2

도시가 모두 convex hull 에 포함되어있으면 n² 이므로 당연히 시간초과가 납니다. 이 문제를 풀려면 rotating calipers알고리즘 알아야합니다.

wagurano 4년 전 2

긴터널끝에한줄의 빛. 그댄 나의 빛. 공부하겠습니다 :)

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

문제

문제

출처

ICPC

고속도로 10254 답이 없어요...

wagurano 4년 전 0

kyo20111 4년 전 2

wagurano 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말