- 이 경우, 5 2 1 3처럼 1->3을 스트레이트로 가는 경우만 허용하고, 4 1 2 3처럼 1->3 사이에 2가 껴 있는 경우는 허용하지 않아도 할 말이 없습니다.
* 1-3 간선은 1-2 간선, 2-3 간선의 합집합과 동일하다 (현 상태)
따라서 분명하게 명시해야 한다고 생각하고, 아래의 문장을 입력 조건 끝에 추가해 주세요.
An edge can pass some points which are not two endpoints. In this case, you should properly divide the edge into 2 or more "unit" edges. For example, if an edge 1 3 is given, you have 2 edges, 1 2 and 2 3.
Wikipedia에 따르면 기하 그래프(geographic graph)는 위상 그래프(topological graph)의 한 분류로, 평면 위의 점들을 선분들로 연결한 그래프를 뜻합니다. 또한 위상 그래프에서는 일반적으로 어떤 간선도 양 끝점이 아닌 다른 정점을 지나지 않음이 보장됩니다. 이를 받아들여, 만약 지금 1 3과 같이 한 간선이 양 끝점이 아닌 다른 점을 지나는 경우가 데이터에 포함되어 있다면 그런 테스트 케이스를 전부 삭제했으면 좋겠습니다.
portableangel 4년 전 3
예제에는 항상 한 칸 떨어진 간선만 존재하고, 본문에도 별다른 언급이 없어서 알 수 없는 부분입니다.
입력에 두 칸 떨어지고 사이에 점이 있는 간선이 있을 경우, 예를 들어 1-3 간선이 입력될 경우 1-2, 2-3 간선으로 분할해서 봐야 합니다.
합리적으로 그렇게 추론할 수 있지 않느냐? 라면 아래의 반론을 봐 주세요.
만약 1-3 간선이 입력된다면 아래의 두 가지 방향으로 아무 문제 없이 해석 가능합니다. 문제에 간선의 정의에 대해 명시하지 않았기 때문입니다.
* 1-3 간선은 1-2 간선, 2-3 간선의 합집합과 다른, 말 그대로의 1-3 간선이다.
- 이 경우, 5 2 1 3처럼 1->3을 스트레이트로 가는 경우만 허용하고, 4 1 2 3처럼 1->3 사이에 2가 껴 있는 경우는 허용하지 않아도 할 말이 없습니다.
* 1-3 간선은 1-2 간선, 2-3 간선의 합집합과 동일하다 (현 상태)
따라서 분명하게 명시해야 한다고 생각하고, 아래의 문장을 입력 조건 끝에 추가해 주세요.
An edge can pass some points which are not two endpoints. In this case, you should properly divide the edge into 2 or more "unit" edges. For example, if an edge 1 3 is given, you have 2 edges, 1 2 and 2 3.