kiwiyou   2년 전

1.

> 데이터 수합 영역은 일반적으로 $N$대의 주변 차량으로 이루어진 볼록 다각형 모양이다.

일반적이지 않은 경우가 이후 등장하는 $N=1, 2$뿐이라는 보장이 없습니다. 따라서 데이터 수합 영역은 잘 정의되지 않은 용어입니다. (1)

다만 대회 중 질문으로 $N=1, 2$만이 예외라는 답변을 받았으므로, $N \ge 3$인 경우 $N$대의 주변 차량으로 이루어진 볼록 다각형 모양으로 정의되는 것으로 보입니다.

2.

데이터 수합 영역은 볼록 다각형이어야 하며, 주변 차량을 기준으로 정의됩니다. 그런데 주변 차량의 위치는 볼록 다각형이 아닐 수 있습니다.

이때 데이터 수합 영역이 정의되지 않는 것인지, 주변 차량의 위치가 애초에 볼록 다각형으로만 주어지는지 (1)과 더불어 지문에서 명확하지 않습니다.

3.

>  $P_i$는 모두 다른 정수 좌표의 점이며, 반시계 방향 순서로 주어진다.

현재 지문에서 주변 차량의 위치는 데이터 수합 영역을 이룰 수도, 이루지 않을 수도 있기 때문에 "반시계 방향"은 잘 정의되지 않습니다.

1., 3.이 해소되지 않으면 문제를 풀 수 없습니다.

2.에 대하여 현재 지문대로라면 83600754 번 제출이 틀려야 하며, 코드로 첨부한 데이터가 추가되어야 합니다.

lighter   2년 전

출제자입니다.

맥락 상 주변 차량이 이루는 점이 모두 볼록 다각형의 꼭짓점이고, 이러한 점들이 반시계방향을 이룬다는 것을 언급하고 싶었습니다.

1. "일반적으로"라는 워딩은 N >= 3일때임을 언급하고 싶었던 내용입니다. 이는 대회 도중의 답변으로 이야기를 했습니다.

2. 마찬가지로, "일반적으로 N대의 주변 차량으로 이루어진 볼록 다각형 모양이다."라는 문장 또한 주변 차량이 모두 볼록 다각형의 꼭짓점이라는 것을 언급하고 싶었던 문장입니다. 주어지는 점의 좌표는 총 N개이기 때문에, 주변 차량의 위치가 볼록 다각형의 내부 혹은 외부에 있다면 볼록 다각형이 N대의 주변 차량으로 이루어졌다는 말이 잘못된 표현이 됩니다. 또한, 볼록 다각형의 변 위에 있다면 입력부에서 서로 다른 세 점이 한 직선 위에 놓이지 않는다는 조건에 위배됩니다. 명시적으로 주변 차량이 볼록 다각형의 꼭짓점이라는 언급은 하지 않았으나, 이에 대한 정보는 그림을 통해 충분히 해석할 수 있다고 판단했습니다.  

3. 위에서 말한 내용과 같습니다.

kiwiyou   2년 전

1. 문제에 해당 내용이 나와 있어야 합니다.

2. 볼록 다각형이 N대의 주변 차량으로 이루어져 있다는 말의 다른 해석은, N대의 주변 차량의 convex hull 정도가 있을 수 있을 것 같습니다.

꼭짓점이라는 말이 지문에 없고, 그림의 주변 차량의 convex hull은 주변 차량을 꼭짓점으로 하는 다각형과 일치합니다. 따라서 그림은 주변 차량이 convex hull 안쪽에 있는 경우를 커버하지 못합니다. 또한, 그림에서 정의를 명확히 내리지 못하고 있을 뿐만 아니라 그림으로 정의를 갈음한다는 내용이 지문에 전혀 없으므로 이 문제에서 그림은 정의를 대체할 수 없습니다.

또한, "주변 차량이 볼록 다각형을 이룬다"가 아닌 "데이터 수합 영역이 볼록 다각형이다"인 데다가 지문에서 위험 영역과 안전 영역이 정의되지 않는 경우까지 설명하고 있기 때문에 주변 차량이 볼록 다각형을 이루지 않는 경우는 문제에서 충분히 고려할 수 있습니다.

yclock   1년 전

@lighter

결론이 뭘까요? 지문을 여러 번 읽어도, <P_1, ..., P_N>이 Convex hull을 구성한다는 게 보장 안된다고 느껴집니다.

만약 이것이 보장된다면, 지문 수정이 필요하고요.

lighter   1년 전

@yclock
이미 해당 내용으로 주변 차량이 볼록다각형의 꼭짓점이라는 내용을 추가해서 수정한 상태인데, 어느 부분에서 보장이 안된다고 느껴지나요? 지문 수정이 필요한 부분을 언급해주시면 감사하겠습니다.

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