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

发布于 2019-05-17  8 次阅读


题目描述

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


思路

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


#include 
#include 
#include 
#include 
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x=c.x&&max(a.y,b.y)>=c.y;
}
double find1(arr a,arr b)
{
    double m=sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
    return m;
}
double cros(arr a,arr b,arr c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
int spfa()
{
    int i;
    queue  t;
    t.push(1);
    state[1]=0;
    exits[1]=true;
    do
    {
        int tt=t.front();
        t.pop();
        i=ls[tt];
        while (i!=0) 
        {
            if (state[tt]+e[i].w
]]>