글 읽기 - 40%에서 시간초과 나는데 확인 해주세요~~~

soimil 4년 전 0

40%에서 시간초과가 나네요.ㅠㅠ

convext hull을 만들고 최단거리를 구했는데,

어떤 부분에서 속도를 줄여야 될까요?ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;

public class Main {

	//static int ans; 
	static int N;
	static Point05[] P;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer token = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(token.nextToken());
		
		for(int tc=1; tc<=T; tc++) {
			
			token = new StringTokenizer(br.readLine());
			N = Integer.parseInt(token.nextToken());
			P = new Point05[N+2];

			for(int i=1; i<=N; i++) {
				token = new StringTokenizer(br.readLine());
				long xx = Long.parseLong(token.nextToken());
				long yy = Long.parseLong(token.nextToken());
				
				P[i] = new Point05(xx, yy);
				
				if(P[1].compareTo(P[i]) > 0 ){
	            	Point05 temp = P[1];
	            	P[1] = P[i];
	            	P[i] = temp;
	            }
			}
			
			for(int i=1; i<=N; i++){
	            if(P[1].compareTo(P[i]) > 0 ){
	            	Point05 temp = P[1];
	            	P[1] = P[i];
	            	P[i] = temp;
	            }
	        }
			
			
			//각정렬
			Arrays.sort(P, 2, N+1, new Comparator<Point05>() {
				@Override
				public int compare(Point05 a, Point05 b) {
					int v = ccw(P[1], a, b);
	                if( v > 0)    return -1;
	                if( v < 0)    return 1;
	                if(dist(P[1], a) < dist(P[1], b)) {
	                	return -1;
	                }else {
	                	return 1;
	                }
				}
				
				
			});
			
			ArrayList<Integer> stack = new ArrayList<Integer>();
			
			stack.add(1);
			stack.add(2);
			
			int top = 2;
			
			P[N+1] = P[1];
			
			for(int i=3; i<=N+1; i++) {
				while(top>=2 && ccw(P[stack.get(top - 2)], P[stack.get(top - 1)], P[i]) <=0) {
					stack.remove(top-1);
					top--;
				}
				
				if(i==N+1) {
					break;
				}
				
				stack.add(i);
				top++;
			}
			
			//stack에 담긴 점들끼리 거리를 구한다.
			long ddd = 0;
			long ans = 0;
			int xxx = 0;
			int yyy = 0;
			int p = 0;
			for(int i=0; i<stack.size(); i++) {
				
				while(p+1<stack.size() && chk(P[stack.get(i)], P[stack.get(i+1)]
						                    , P[stack.get(p)], P[stack.get(p+1)])) {
					
					ddd = dist(P[stack.get(i)], P[stack.get(p)]);
					if(ddd>ans) {
						ans = ddd;
						xxx = i;
						yyy = p;
					}
					
					p++;
				}
				
				ddd = dist(P[stack.get(i)], P[stack.get(p)]);
				
				if(ddd>ans) {
					ans = ddd;
					xxx = i;
					yyy = p;
				}
			}
			
			bw.write(P[stack.get(xxx)].x + " " + P[stack.get(xxx)].y + " " + P[stack.get(yyy)].x + " " + P[stack.get(yyy)].y + "\n");
			bw.flush();
		}
	}
	
	public static boolean chk(Point05 a, Point05 b, Point05 c, Point05 d) {
		Point05 xx = new Point05(a.x-b.x, a.y-b.y);
		Point05 yy = new Point05(c.x-d.x, c.y-d.y);
		Point05 zz = new Point05(0, 0);
		
		return ccw(zz, xx, yy) >= 0 ;
	}
	
	public static long dist(Point05 a, Point05 b) {
		long aa = (a.x - b.x)*(a.x - b.x) + (a.y-b.y)*(a.y-b.y);
		return aa;
	}
	
	public static int ccw(Point05 a, Point05 b, Point05 c) {
		long ccw1 = a.x*b.y + b.x*c.y + c.x*a.y;
		long ccw2 = a.x*c.y + c.x*b.y + b.x*a.y;
				
		long ccwvalue = ccw1 - ccw2;
		
		if(ccwvalue < 0) {
			return -1;
		}else if(ccwvalue > 0){
			return 1;
		}else {
			return 0;
		}
	}
	
}

class Point05 implements Comparable<Point05>{
	long x, y;
	Point05(long x, long y){
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Point05 that) {
		if(this.y == that.y) {
			if(this.x < that.x) {
				return -1;
			}else {
				return 1;
			}
			
		}else {
			if(this.y < that.y) {
				return -1;
			}else {
				return 1;
			}
			
		}
		
	}
}

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

문제

문제

출처

ICPC

40%에서 시간초과 나는데 확인 해주세요~~~

soimil 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말