글 읽기 - 볼록 껍질 ㅠㅠ

hhhrock7 5년 전 0

안녕하세요

볼록 껍질 관련 질문 글은 전부 다봤는데요

거기 나온 샘플은 다 성공인데, 막상 제출하면 fail 이네요ㅠㅠ

코드에서 어디가 문제인지 아신다면 답변 좀 부탁 드립니다 ㅠㅠ

감사합니다

import java.util.Scanner;

public class Main {
	static Point minP;	
	static int stackSize = 0;
	static Point[] stack;
	static Point[] p;
	
	static class Point {
		int x,y;
		public Point(){}
	}
	
	static long ccw(Point a, Point b, Point c) {
		return (a.x*b.y + b.x*c.y + c.x*a.y) - (a.y*b.x + b.y*c.x + c.y*a.x);
	}
	
	static void build(Point[] arr, int size) {
		for(int i=size/2; i >= 0; i--) {
			maxheapify(arr, size, i);
		}
	}
	
	static void heapsort(Point[]arr, int size) {
		build(arr, size);
		for(int i=size-1; i >= 0; i--) {
			swap(arr, i, 0);
			maxheapify(arr, i, 0);
		}
	}
	
	static long compareP(Point a, Point b) {
		return ccw(minP, a, b);
	}
	
	static void swap(Point[]arr, int a, int b) {
		Point temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	
	static void maxheapify(Point[]arr, int size, int i) {
		int child = i;

		int left = i * 2;
		int right = i * 2 + 1;

		if (left > size || right > size)
			return;

		if (left < size && compareP(arr[left], arr[child]) < 0)
			child = left;
		else if (left < size && compareP(arr[left], arr[child]) == 0) {
			long a = getDistance(minP, arr[left]);
			long b = getDistance(minP, arr[child]);
			if (a > b) {
				child = left;
			}
		}
		if (right < size && compareP(arr[right], arr[child]) < 0)
			child = right;
		else if (right < size && compareP(arr[right], arr[child]) == 0) {
			long a = getDistance(minP, arr[right]);
			long b = getDistance(minP, arr[child]);
			if (a > b) {
				child = right;
			}
		}

		if (compareP(arr[i], arr[child]) < 0)
			return;
		else if (i == child && compareP(arr[i], arr[child]) == 0) {
			return;
		}

		swap(arr, i, child);
		maxheapify(arr, size, child);
	}
	
	static Point getMinP(Point[]arr) {
		Point minP = new Point();
		minP.x = minP.y = 100000000;
		
		for(int i=0; i < arr.length; i++)
			if (minP.y > arr[i].y)
				minP = arr[i];
		
		for(int i=0; i < arr.length; i++)
			if (minP.y == arr[i].y)
				if (minP.x > arr[i].x)
					minP = arr[i];
		
		return minP;
	}
	
	static long getDistance(Point a, Point b) {
		return (b.y - a.y)*(b.y - a.y) + (b.x - a.x)*(b.x - a.x);
	}
	
	static void push(Point p) {
		stack[stackSize++] = p;
	}
	
	static void pop() {
		stack[--stackSize] = null;
	}
	
	public static void main (String [] args) {
		Scanner sc = new Scanner(System.in);
		
		try {
			sc = new Scanner(new java.io.File("sample_input.txt"));
		} catch (java.io.FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
//		int testcases = sc.nextInt();
		int testcases = 1;
		for(int tc = 1; tc <= testcases; tc++) {
			int N = sc.nextInt();
			p = new Point[N];
			stack = new Point[N];
			stackSize = 0;
			
			for(int i=0; i < N; i++) {
				p[i] = new Point();
				p[i].x = sc.nextInt();
				p[i].y = sc.nextInt();
			}
	
			minP = getMinP(p);
			heapsort(p, p.length);
			
			int count = 0;
			push(minP);
			push(p[count++]);
	
			while (count < N) {
				while (stackSize >= 2 && ccw(stack[stackSize-2], stack[stackSize-1], p[count]) <= 0)
					pop();
				push(p[count++]);
			}
			
//			System.out.println("#" + tc + " " + stackSize);
			System.out.println(stackSize);
		}
	}
}

djm03178 5년 전 1

Point.x, Point.y는 int형입니다. 그래서 15번째 줄은 전부 int로 계산되므로 중간 과정에서 오버플로가 생길 수 있습니다. 리턴은 long으로 하셨지만, 모든 연산에는 중간 과정마다 전부 타입이 있고 그 중에 한 번이라도 오버플로가 발생하면 뒤늦게 형변환을 해도 늦습니다.

hhhrock7 5년 전 0

와!! 대박입니다 그것만 바꾸니 바로 성공하네요!

djm03178 님 정말 감사합니다^^

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

문제

문제

출처

ICPC

볼록 껍질 ㅠㅠ

hhhrock7 5년 전 0

djm03178 5년 전 1

hhhrock7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말