글 읽기 - 생성되는 수직선, 수평선의 개수는 N/2개가 아닌가요?

(追記) (追記ここまで)

생성되는 수직선, 수평선의 개수는 N/2개가 아닌가요?

17611번 - 직각다각형

wjp1230 5달 전 0

문제의 조건인 단순직각다각형에서

수평선, 수직선의 개수는 항상 꼭짓점의 1/2 이라고 생각했습니다.

그런데 아래 코드, 배열 크기가 N/2인 경우 Index out of bounds 에러,

크기를 N 으로 설정했을 때는 통과가 됐습니다.

한 직선상에서 방향만 바뀌는, 그러니까 수직/수평선만 생기는 케이스가 있는 것이라고 결론을 내렸는데,

그렇다면 문제의 조건인 단순직각다각형-다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형-을 만족하지 않는 것 같습니다.

혹시 제 생각이 잘못된 것인지, 여러분들의 의견을 여쭙고 싶습니다.

/* 
 * 수직선, 수평선은 각 N / 2 개씩 생긴다. (점 2개를 이어야 선분 1개)
 * 꼭짓점을 입력받으며 수직, 수평선을 배열에 저장한다. <처음, 끝>
 * 입력이 끝나면 처음 좌표 기준으로 정렬
 * 
 * PQ에 끝 좌표를 넣으며 최대 overlapping 되는 개수를 구한다.
 * 다음 선분의 시작 위치가, 최소 heap 에 들어 있는 위치 보다 작으면 겹치는 경우.
 * 크거나 같으면 겹치지 않는 경우다.
 * 
 * N <= 100,000 이므로, 정렬 + 각 선분마다 (N) * pq 삽입 삭제 = O(N log N) 충분함.
 * 
 */
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
 public static void main(String[] args) throws IOException {
 int N = readInt();
 Line[] vertical = new Line[N >> 1], horizon = new Line[N >> 1];
 int prevX = readInt(), prevY = readInt(), curX, curY, idxV = 0, idxH = 0, startX = prevX, startY = prevY;
 for (int i = 1; i < N; i++) {
 curX = readInt();
 curY = readInt();
 if (prevX == curX && prevY != curY) // 길이 0이 아닌 수직선만
 vertical[idxV++] = new Line(prevY, curY);
 else if (prevY == curY && prevX != curX) // 길이 0이 아닌 수평선만
 horizon[idxH++] = new Line(prevX, curX);
 prevX = curX;
 prevY = curY;
 }
 if (prevX == startX && prevY != startY)
 vertical[idxV++] = new Line(prevY, startY);
 else if (prevY == startY && prevX != startX)
 horizon[idxH++] = new Line(prevX, startX);
 int max = 0;
 if (idxH > 0) {
 Arrays.sort(horizon, 0, idxH);
 PriorityQueue<Integer> pq = new PriorityQueue<>();
 for (int i = 0; i < idxH; i++) {
 while (!pq.isEmpty() && pq.peek() <= horizon[i].start)
 pq.poll();
 pq.offer(horizon[i].end);
 max = Math.max(max, pq.size());
 }
 }
 if (idxV > 0) {
 Arrays.sort(vertical, 0, idxV);
 PriorityQueue<Integer> pq = new PriorityQueue<>();
 for (int i = 0; i < idxV; i++) {
 while (!pq.isEmpty() && pq.peek() <= vertical[i].start)
 pq.poll();
 pq.offer(vertical[i].end);
 max = Math.max(max, pq.size());
 }
 }
 System.out.println(max);
 }
 static class Line implements Comparable<Line> {
 int start, end;
 public Line(int a, int b) {
 this.start = Math.min(a, b);
 this.end = Math.max(a, b);
 }
 @Override
 public int compareTo(Main.Line o) {
 return this.start - o.start;
 }
 }
 static int pos, len;
 static byte[] buf = new byte[8192];
 static byte read() throws IOException {
 if (pos == len) {
 len = System.in.read(buf);
 pos = 0;
 }
 return buf[pos++];
 }
 static int readInt() throws IOException {
 int c;
 while ((c = read()) <= 32)
 ;
 boolean negative = c == 45;
 if (negative)
 c = read();
 int n = c & 15;
 while ((c = read()) > 47)
 n = (n << 3) + (n << 1) + (c & 15);
 return negative ? -n : n;
 }
}

lollipop03 5달 전 2

https://www.acmicpc.net/board/...

이런 케이스도 참고해 보셨을까요

wjp1230 5달 전 1

아.. 꼭지각이 180도인 점도 꼭짓점이 될 수가 있군요

감사합니다 !

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC