글 읽기 - 17611 직각 다각형 반례

ybc125 1년 전 0

x1 == x2 일 때 해당 x1 또는 x2 좌표는 걸칠 수 없으므로 sorting에 영향을 주지 않는 음수값 넣고

똑같은 논리로 y1, y2일 떄 그렇게 넣고

누적합 배열 만든 뒤 정렬해서 0번째 인덱스에 있는 값이 답이다라는 논리로 코드를 짰습니다.

수평, 수직선은 정수가 아닌 실수도 가능하기에 좌표 *2를 해서 0.5부분에 걸칠 수 있게 코드를 짰는데요.

13%에서 계속 틀리는데 이왜틀을 시전하고 있는 상황입니다. 반례나 문제 해결에 도와주세요 ㅜㅜ

package 이진탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Boj_17611_직각다각형 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// x1, y1 / x2, y2 / x3, y3 / x4, y4
		
		// x1 == x2 =? 같은 수직선 상에 놓임
		// y1 == y2 =? 같은 수평선 상에 놓임
		
		// 탐색을 하다가 숫자가 가장 높은 경우를 찾음
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int hori[][] = new int[1000001*2][2];
		int vert[][] = new int[1000001*2][2];
		
		int prvX = 0;
		int prvY = 0;
		int curX = 0;
		int curY = 0;
		
		// 배열 초기화
		for (int i = 0; i < hori.length; i++) {
			hori[i][0] = i;
			vert[i][0] = i;
		}
		
		// 점 좌표 입력 후 counting 처리
		for (int i = 0; i < n; i++) {
			String temp[] = br.readLine().split(" ");
			if(i != 0) {
				curX = (Integer.parseInt(temp[0]) + 500000)*2;
				curY = (Integer.parseInt(temp[1]) + 500000)*2;
				if(prvX == curX) {
					for (int j = Math.min(prvY, curY); j <= Math.max(prvY, curY) ; j++) {
						vert[j][1]++;
					}
					vert[prvY][1]--;
					hori[prvX][1] = -10000000;
					hori[curX][1] = -10000000;
				}else if(prvY == curY) {
					for (int j = Math.min(prvX, curX); j <= Math.max(prvX, curX) ; j++) {
						hori[j][1]++;
					}
					hori[prvX][1]--;
					vert[prvY][1] = -10000000;
					vert[curY][1] = -10000000;
				}
				prvX = curX;
				prvY = curY;
			}else {
				prvX = (Integer.parseInt(temp[0]) + 500000)*2;
				prvY = (Integer.parseInt(temp[1]) + 500000)*2;
			}
		}
		
		Arrays.sort(hori, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1]- o1[1];
			}
		});
		
		Arrays.sort(vert, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1] - o1[1];
			}
		});
		
		System.out.print(Math.max(hori[0][1], vert[0][1]));
		
		
			
	}
}

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

문제

문제

출처

ICPC

17611 직각 다각형 반례

ybc125 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말