글 읽기 - 고수님의 도움을 구합니다....

cuhcuh1 6년 전 0

먼저 입력을 받으며 제일 아래쪽에 있는 점을 기준으로 삼습니다. (동일한 높이에 좌표가 있다면 좌측 점을 기준)
그 후에 그 점을 기준으로 하는 정렬을 합니다. (내적을 이용해 값 비교, 동일한 각을 가진다면 거리가 짧은 순으로)
정렬 후, 스택에 넣고 한 점씩 왼쪽에 있는지 확인합니다.

제가 생각 할 수 있는 입력에 대해선 다 통과를 하는데 채점시 가차없이 9퍼센트에서 틀려버리네요...
무엇이 잘못됬는지, 예외케이스라도 던져주시면 정말 감사하겠습니다. ㅠㅠ 몇일동안 고민해도 답이 안나오네요...

import java.io.*;
import java.util.*;

class Main {

	static int n;
	static ArrayList<point> arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());

		arr = new ArrayList<point>();
		n = Integer.parseInt(tk.nextToken());
		int compY = 40000;
		int compX = 40000;
		int index = 0;
		for(int i = 0; i < n; i++) {
			tk = new StringTokenizer(br.readLine());
			int tx = Integer.parseInt(tk.nextToken());
			int ty = Integer.parseInt(tk.nextToken());
			arr.add(new point(tx, ty));
			if(compY > ty) {
				compY = ty;
				compX = tx;
				index = i;
			} else if(compY == ty && compX > tx) {
				compY = ty;
				compX = tx;
				index = i;
			}
		}

		point std = new point(arr.get(index));
		arr.remove(index);
		Collections.sort(arr, new angleSort(std));
		
		Stack<point> st = new Stack<point>();
		st.push(std);
		st.push(arr.get(0));

		for(int i = 1; i < arr.size(); i++) {
			while(st.size() >= 2) {
				point b = st.pop();
				point a = st.peek();
				point c = arr.get(i);

				point v1 = new point(b.x - a.x, b.y - a.y);
				point v2 = new point(c.x - a.x, c.y - a.y);

				long com = cal(v1, v2);
				if(com > 0) {
					st.push(b);
					break;
				}
			}

			st.push(arr.get(i));
		}

        int ans = st.size();
		for(int i=0; i<ans; i++) {
			System.out.printf("[%d, %d]", st.peek().x, st.peek().y);
			st.pop();
		}
		System.out.println();
		System.out.println(ans < 2 ? 2 : ans);
	}

	static long cal(point v1, point v2) {
		return (long)v1.x * (long)v2.y - (long)v1.y * (long)v2.x;
	}

	static class point {
		int x, y;
		point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		point(point a) {
			x = a.x;
			y = a.y;
		}
	}

	static class angleSort implements Comparator<point> {

		private point std;

		angleSort(point std) {
			this.std = new point(std.x, std.y);
		}

		@Override
		public int compare(point a, point b) {
			int datA = a.x - std.x;
			int datB = b.x - std.x;

			double cosA = datA / Math.sqrt(datA * datA + (a.y - std.y) * (a.y - std.y));
			double cosB = datB / Math.sqrt(datB * datB + (b.y - std.y) * (b.y - std.y));

			int retA = (int)(cosA * 1000);
			int retB = (int)(cosB * 1000);

			if(retB != retA) {
				return retB - retA;
			} else {
				long dA = datA * datA + (a.y - std.y) * (a.y - std.y);
				long dB = datB * datB + (b.y - std.y) * (b.y - std.y);
				return dA - dB < 0 ? -1 : 1;
			}
		}
	}
}

dohoon 3년 전 0

제가 java는 컴파일할 여력이 안 되지만,

테스트 케이스 하나는 공유하겠습니다.

원래 답 : 6

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

문제

문제

출처

ICPC

고수님의 도움을 구합니다....

cuhcuh1 6년 전 0

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말