题目描述

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

思路

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

#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
#define INF 0x7f7f7f7f
#define maxn 182409
using namespace std;
struct arr
{
    int x,y;
}a[2][maxn];
int ls[maxn],exits[maxn];
double state[maxn];
struct edge
{
    int x,y;
    double w;
    int next;
}e[maxn];
arr r;
int find(arr a,arr b,arr c)
{
    return min(a.x,b.x)<=c.x&&min(a.y,b.y)<=c.y&&max(a.x,b.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 <int> 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<state[e[i].y])
            {
                state[e[i].y]=state[tt]+e[i].w;
                if (exits[e[i].y]==false)
                {
                    t.push(e[i].y);
                    exits[e[i].y]=true;
                }
            }
            i=e[i].next;
        }
        exits[tt]=false;
    }
    while (!t.empty());
}
int main()
{
    int rx,ry,n,m;
    scanf("%d%d%d%d",&a[0][0].x,&a[0][0].y,&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[0][i].x,&a[0][i].y);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&a[1][i].x,&a[1][i].y);
    int l=0;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            if (i!=j)
            {
                int fl=0;
                for (int k=1;k<=m;k++)
                    if (!i||!j||!cros(a[0][i],a[0][j],a[1][k])&&find(a[0][i],a[0][j],a[1][k]))
                    {
                        fl=1;
                        break;
                    }
                if (fl==1)
                {
                    e[++l]=(edge){i,j,2.0*find1(a[0][i],a[0][j]),ls[i]};
                    ls[i]=l;
                }
                else
                {
                    e[++l]=(edge){i,j,find1(a[0][i],a[0][j]),ls[i]};
                    ls[i]=l;
                }
            }
    for (int i=0;i<maxn;i++)
        state[i]=INF*1.0;

    spfa();

    printf("%d\n",(int)(state[0]+0.5));
}