Smoking gun (UVa Live Archive Europe Northwestern 2011)

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)は距離