2012-06-12 Smoking gun (UVa Live Archive Europe Northwestern 2011) UVa Live Archive Online Judge http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3917 問題 人がn人いて、それぞれ(xi,yi)にいる。ある人が、ある人の銃声を別の人の銃声よりも早く聴いたという情報がm個与えられる。どの順番で銃を撃ったか答えよ。 2<=n<=100 1<=m<=1,000 解法 aがbの銃声をcよりも先に聴いたとする。するとこれは不等式とみなせて、不等式をグラフに直すとc→bへ重みabs(a - c) - abs(a - b)の辺ができる*1。このグラフに負閉路があるならIMPOSSIBLE、i→j と j→iがともに0以上ならUNKNWONとなる。あとは値の最も小さいものから銃を撃ったことにすれば良い。 *1:abs(a - c)は距離