글 읽기 - 볼록껍질 9%에서 런타임 오류가 나는데, 도움 부탁드립니다.

popuur 6년 전 0

볼록껍질 9%에서 런타임 오류가 발생합니다.

어느부분이 잘못되었을까요?

그리고 테스트를 해볼만한 예제가 더 있을까요?

좌표는 ArrayList에 저장하고,

좌표 정렬은 Collection.Sort를 이용했습니다.

ConvexHull 저장 자료구조는 Stack을 사용했습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;


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

public class Main {
	
	/*
	 * 볼록 껍질
	 * https://www.acmicpc.net/problem/1708
	 */
	
	static int MINY;
	static int MINX;

	public static void main(String[] args) throws IOException {
		

		/*
		 * 1. Convex hull 생성
		 * 1) 최하단, 좌측점을 기준
		 * 2) 점을 각도순으로 정렬
		 * 3) CCW사용
		 * 3.2) 양수 > 0 : STACK에 다음점을 넣고 PASS
		 * 3.3) 음수 < 0 : STACK의 마지막 원소 제거, repeat
		 */
		
		//System.setIn(new FileInputStream("res/seminar/convex.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Edge> A = new ArrayList<Edge>();
		
		StringTokenizer ST;
		MINY = Integer.MAX_VALUE;
		MINX = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++){
			ST = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(ST.nextToken());
			int y = Integer.parseInt(ST.nextToken());
			
			// 1) 최하단, 좌측점을 기준
			if (y < MINY){
				MINY = y;
				MINX = x;
				 
			} else if (y == MINY){
				if (x < MINX){
					MINY = y;
					MINX = x;
				}
			}
			A.add(new Edge(x, y));
		}
		
		// 2) 점을 각도순으로 정렬
		Collections.sort(A, new Comparator<Edge>() {

			@Override
			public int compare(Edge arg0, Edge arg1) {
				long ret = ccw(MINX, MINY, arg0.x, arg0.y, arg1.x, arg1.y);
				
				if (ret > 0){
					return -1;
				} else if (ret < 0){
					return 1;
				}
				
				long a = dist(MINX, MINY, arg0.x, arg0.y);
				long b = dist(MINX, MINY, arg1.x, arg1.y);
				
				if (a < b){
					return -1;
				} else if (a > b){
					return 1;
				}				
				
				return 0;
			}
		});
		
		/*
		 * 4) STACK과 CCW사용
		 * 4.1 CCW(STACK의 마지막 두점, 다음점)
		 * 4.2 양수 > 0 : STACK에 다음점을 넣고 PASS
		 * 4.3 음수 < 0 : STACK의 마지막 원소 제거, repeat
		 */
		
		A.add(new Edge(MINX, MINY));
		Edge  XY2 = null, XY1 = null, NEXT = null;
		Stack<Edge> CVH = new Stack<Edge>();
		
		//0번점, 1번점 stack에 push
		CVH.push(A.get(0));
		CVH.push(A.get(1));
		
		
		for (int i = 2; i < N; i++) {
			while (CVH.size() >= 2){
				NEXT = A.get(i);
				XY2 = CVH.pop();
				XY1 = CVH.peek();				
				
				if (ccw(XY1.x, XY1.y, XY2.x, XY2.y, NEXT.x, NEXT.y) > 0){
					CVH.push(XY2);
					break;
				} 
			}
			CVH.push(NEXT);
		}
		bw.write(CVH.size()+"\n");
		
		br.close();
		bw.flush();
		bw.close();
	}
	
	static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
		long ret = (x1 * y2 + x2 * y3 + x3 * y1) - (x3 * y2 + x2 * y1 + x1 * y3);

		if (ret > 0)
			return 1;
		else if (ret == 0)
			return 0;
		else
			return -1;
	}

	static long dist(int x1, int y1, int x2, int y2) {
		return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
	}

}

lll4592 6년 전 1

ccw와 dist 계산 과정에서 overflow가 발생합니다

popuur 6년 전 0

답변 감사합니다.

ccw와 distance 계산에서 int로 받아주는부분을 long으로 모두 변환하니 되었습니다.

감사합니다.

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

문제

문제

출처

ICPC

볼록껍질 9%에서 런타임 오류가 나는데, 도움 부탁드립니다.

popuur 6년 전 0

lll4592 6년 전 1

popuur 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말