글 읽기 - 런타임 에러가 발생하는데 어느부분에서 문제인지 모르겠습니다.

popuur 6년 전 0

런타임 에러가 발생하는데,

어느부분을 확인해바야 할까요?

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

			@Override
			public int compare(Point arg0, Point 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;
			}
		});
		
		
		/*
		 * 3. STACK과 CCW사용
		 * 3.1 CCW(STACK의 마지막 두점, 다음점)
		 * 3.2 양수 > 0 : STACK에 다음점을 넣고 PASS
		 * 3.3 음수 < 0 : STACK의 마지막 원소 제거, repeat
		 */

		Stack<Point> CVH = new Stack<Point>();
		CVH.push(A.get(0));
		CVH.push(A.get(1));
		
		int index = 1;
		while(index < N){
			if (CVH.size() < 2){
				index++;
				continue;
			}
			
			Point XY2 = CVH.pop();
			//Point XY1 = CVH.pop();
			Point XY1 = CVH.peek();
			Point NEXT = A.get(index);
			
			long check = ccw(XY1.x, XY1.y, XY2.x, XY2.y, NEXT.x, NEXT.y);
			
			if (check <= 0){
				CVH.push(NEXT);
				
			} else if (check > 0){
				
				CVH.push(XY2);
				CVH.push(NEXT);
			}
			index++;
		}
		bw.write(CVH.size()+"\n");
			
		br.close();
		bw.flush();
		bw.close();
	}
	
	
	static long 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);
	}
}

slave_holyscar 6년 전 1

바로 위에분 질문과 비슷한 경우인 것 같습니다.

저같은 경우, sort에서 violate general contract 에러가 나더라구요.

바로 윗 질문도 같은 경우구요.

sort할때 comparator에서 문제가 생기는데.......어떻게 해결해야될지 도저히 감이 안잡히네요 ㅠㅠㅠ

popuur 6년 전 1

입력 인자부분을 모두 long형으로 변경해주니까 되었습니다.

violate 에러가 발생한것은 계산을 할때 int범위를 넘으면 -가 되어버려서 비교가 불가능하기때문이라고하네요.

그래서 더큰 long형으로 바꿔주니까 되었습니다.

slave_holyscar 6년 전 0

오 해결되었습니다!

정말 감사합니다 ㅠㅠㅠ

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

문제

문제

출처

ICPC

런타임 에러가 발생하는데 어느부분에서 문제인지 모르겠습니다.

popuur 6년 전 0

slave_holyscar 6년 전 1

popuur 6년 전 1

slave_holyscar 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말