아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Final Defense Line

시간 제한3초메모리 제한512 MB

요약
같은 농도의 가스를 채운 여러 다각형이 주어질 때, 출발점에서 중요 시설까지 이동하는 생물이 받는 최소 피해량을 구한다. 피해는 지나온 구간의 농도 차의 절댓값이다.
난이도

보통10점 중 7점

유형
기하, 그래프, 최단 경로
정답자
아직 제출이 없습니다

문제

たびたび未確認生物に侵略されるようになった某国では重要施設を新型防衛兵器で保護することにした。 この兵器は多角形の領域に特殊なガスを充満させることで未確認生物にダメージを与えることができる。未確認生物が侵攻する途中でガスの濃度が変わると、濃度の差の絶対値のダメージを与える。ガスの濃度が同じ領域を動いているときはダメージは一切発生しない。 現在の技術ではガスの濃度は一定にしかできないので、某国は新型防衛兵器を複数投入することにした。全ての兵器でガスの濃度は同じであり、複数の兵器の領域に含まれる部分は濃度が足し合わされる。 未確認生物の出現地点と重要施設の位置を元に、未確認生物が重要施設まで侵攻する時に受けるダメージの最小値を求めて欲しい。 ただし、未確認生物の侵攻ルートに多角形の頂点や他の多角形との交点は含まれないものとする。また、多角形の辺上を辺にそって侵攻することはない。

입력

入力は以下の形式で与えられる。

多角形の数
多角形の頂点数
x座標 y座標
x座標 y座標
...
多角形の頂点数
x座標 y座標
x座標 y座標
...
出現地点と重要施設のデータの数
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
...

출력

出現地点と重要施設の組ごとに未確認生物が重要施設まで侵攻する際に受けるダメージの最小値を1行ずつ出力せよ。

제한

  • 入力に含まれる座標は絶対値が1,000以下の整数
  • 多角形の数は1以上5以下
  • 多角形の頂点数は3以上5以下
  • 出現地点と重要施設のデータの数は1以上100以下
  • 多角形は与えられた頂点を順につないでできる多角形を指し、自己交差はない
  • 出現地点と重要施設は多角形の頂点及び辺上にあることはない

예제5

  1. 예제 1

    입력
    2
4
0 4
1 1
3 1
4 4
3
6 0
10 0
8 7
1
2 3 9 1
    예상 출력
    2

  2. 예제 2

    입력
    1
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5
    예상 출력
    1
1

  3. 예제 3

    입력
    2
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
1
5 5 15 5
    예상 출력
    0

  4. 예제 4

    입력
    2
3
0 0
10 0
5 10
3
5 0
15 0
10 10
1
5 5 10 5
    예상 출력
    2

  5. 예제 5

    입력
    2
4
0 0
10 0
10 10
0 10
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5
    예상 출력
    2
2