Time Limit: 8 sec / Memory Limit: 64 MB
伝説の剣を破壊した魔王は,ついに勇者をある遺跡に追い詰めた. 既に勇者は袋の鼠であるが,相手は神々の加護を得た勇者である. たとえ伝説の剣がなくとも,いかなる奇跡が奴に味方するかわかったものではない. 魔王も伝説の剣の破壊やこれまでの戦闘で,魔力を大量に消費し,疲弊している. そこで,万全を期すために,強力な使い魔を大量に召喚し,一斉攻撃を仕掛けることにした. しかし,強力な使い魔を使役するには,魔力を大量に消費してしまう. 万が一,勇者が使い魔による総攻撃を突破した場合に備え,できるだけ魔力を温存したい. そこで,入り口から使い魔を一度に突入させ,何体の使い魔が一斉に勇者を攻撃できるのか調べることになった.
魔王の右腕であるあなたは,低級な使い魔を召喚し,遺跡の構造を調べさせた. しかし,低級な使い魔を利用したためか,報告された内容は非常にわかりづらいものとなってしまった. このままでは役に立たないので,仕方なく使い魔の報告を分析することにした.
まず,遺跡の入口についてだが,複数の入口がある. これらの入口は,必ず通路の端またはいくつかの通路が交差した場所にあることがわかった. また,勇者は入口ではない通路の端か交差した場所にいるようだ.
そして,問題は遺跡内の通路である. この遺跡には魔術的な結界やガーディアンなどは存在しないが,通路が複雑に入り組んでいる. 幸いといっていいのか,通路には特に一方通行系のトラップや, 一度通った通路が二度と通れなくなるようなトラップは存在しないようだ. もちろん,入る度に遺跡内部全体の構造が変わってしまうようなトラップもない. 使い魔たちは,各通路の情報を,遺跡の中にある通路の2つの端点の座標と, この通路を同時に通ることができる使い魔の数という形で報告してきた.
|
使い魔の報告した遺跡内の通路同士は,交差することがある. 二つの通路が一点で交わる場合に,これを一つの交点として数える. このとき,通れる使い魔の数は,通路の長さに対して比例配分がされる. 例えば図1のように,使い魔が20匹通れる(0,0)と(10,0)を繋ぐ通路に対して, 交点が(4.5,0)にできた場合は,使い魔が9匹通れる(0,0)と(4.5,0)を繋ぐ通路と, 使い魔が11匹通れる(4.5,0)と(10,0)を繋ぐ通路の2つに分割される.
|
さらに,報告された通路同士は重なることがある. このときは重なった通路部分同士の和が使い魔の通れる数になる. 例えば図2のように,使い魔が10匹通れる(0,0)と(10,0)を繋ぐ通路と, 使い魔が20匹通れる(2,0)と(12,0)を繋ぐ通路が与えられたときは, 使い魔が2匹通れる(0,0)と(2,0)を繋ぐ通路と, 使い魔が8+16で24匹通れる(2,0)と(10,0)を繋ぐ通路と, 使い魔が4匹通れる(10,0)と(12,0)を繋ぐ通路に分割される.
報告された通路の情報を基に,分割や併合を行っていくと,計算上通れる使い魔の数に小数が出ることがある. 使い魔は小さくなったり,半分の大きさに分裂したりはできないため,小数部分は切り捨てて考えればよいだろう.
使い魔からの情報をここまで分析したことで,遺跡内の構造が見えてきた. 後は,どれだけの使い魔が一斉に勇者を攻撃できるのか割り出すだけである.
入力は以下の形式で与えられる.
n ax1 ay1 bx1 by1 w1 ・・・ axn ayn bxn byn wn m cx1 cy1 ・・・ cxn cyn dx dy
入力の形式に含まれる各変数の意味と制約は以下の通りである. n(0 < n <=50)は建物内の通路の数を表す.
(axi, ayi)と(bxi, byi) (0 <= axi, ayi, bxi, byi <= 100)はある通路の端点を表す .ここで(axi, ayi)≠(bxi, byi)であることが保証される.またそれぞれの通路に対して,使い魔が wi (0 < wi <= 100)匹通ることができる.
m(0 < m <= 10) は入り口の数を表す.(cxi, cyi)が入り口の位置を, (dx, dy) は勇者が隠れている位置を表す.またcxi, cyi , dx, dyはすべて少数第6位の数値まで与えられる.入口の場所,勇者が隠れている位置は,通路の端点か交点上である.また分割された通路の長さは,0.000001より大きいことが保証されている.
勇者が隠れている位置に,同時に襲うことが出来る使い魔の最大の数を出力せよ.
2 0 0 5 0 10 1 0 6 0 10 1 0.000000 0.000000 6.000000 0.000000
2
2 3 0 7 0 10 0 0 10 0 100 1 0.000000 0.000000 10.000000 0.000000
30
2 0 0 5 5 7 0 5 5 0 4 1 0.000000 0.000000 2.500000 2.500000
3
2 0 0 5 0 9 3 0 8 0 9 1 3.000000 0.000000 5.000000 0.000000
7
10 30 58 43 79 60 16 68 71 61 66 45 59 66 63 63 19 84 28 42 46 45 82 12 76 68 25 57 31 17 59 75 62 18 41 78 32 77 67 18 46 27 89 29 7 32 26 52 14 38 30 4 25.000000 57.000000 61.708447 62.182561 27.000000 89.000000 27.249448 78.772627 36.776964 68.947403
12