SSL 1579_泽泽在巴西_计算几何+spfa

题目描述

没办法,泽泽硬着头皮和足球流氓另外掳来的几个人一起组建了一只队伍,和足球流氓队比赛。
  比赛开始,泽泽队率先发球。泽泽观察了四周,想怎么才能用最短的时间射门呢?
  射门的时间为距离*2,而传球的时间是距离*1。所以泽泽想找一条用时最少的射门路径,来打败足球流氓。
  足球流氓当然不会袖手旁观,他们会拦截。当泽泽队伍中的传球人、被传球人之间有某足球流氓并且他们在同一直线上时,传球不会成功,即不能这样传球。比如A(1,2)想传球给B(7,8),中间有个足球流氓C(3,4),则他们在同一直线,传球不成功。射门不受足球流氓影响。


思路

叉积判断是否在同一直线上,连边跑spfa即可


]]>