Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
泽泽帮助了英国某街道尽量减少酸雨的伤害，街道办主任非常感激他，就把他领到一扇门前，告诉他这扇门能通往好地方，具体
好到什么程度要看泽泽人品。泽泽毫不犹豫地走了进去……
泽泽来到了足球王国——巴西。这可是个好地方，泽泽看来人品攒了不少了。这里大街小巷都在踢足球，其乐无穷。
突然，泽泽被一个人拎了起来，一看，是个足球流氓。他后面跟了一大群足球流氓，正虎视眈眈地看他。他们要求和泽泽比赛
，输了就要揍他。
没办法，泽泽硬着头皮和足球流氓另外掳来的几个人一起组建了一只队伍，和足球流氓队比赛。
比赛开始，泽泽队率先发球。泽泽观察了四周，想怎么才能用最短的时间射门呢？
射门的时间为距离*2，而传球的时间是距离*1。所以泽泽想找一条用时最少的射门路径，来打败足球流氓。
足球流氓当然不会袖手旁观，他们会拦截。当泽泽队伍中的传球人、被传球人之间有某足球流氓并且他们在同一直线上时，传
球不会成功，即不能这样传球。比如A（1，2）想传球给B（7，8），中间有个足球流氓C（3，4），则他们在同一直线，传球不
成功。射门不受足球流氓影响。
【输入格式】
第1行4个整数x0，y0，n，m。x0，y0表示球门的坐标，n表示泽泽队伍有几个人，m表示足球流氓有几个人。 接下来的n行，分别有2个整数，表示泽泽球队的球员坐标。其中最前面的2个整数是泽泽的坐标。球一开始在泽泽脚下。 接下来的m行，分别有2个整数，表示足球流氓的球员坐标。 保证不会有2个人坐标相同。
【输出格式】
输出一个整数，是最短时间四舍五入取整后的结果。
【数据规模】
对于80%的数据，n<=10，m<=5 对于100%的数据，n<=300，m<=100
Sample Input1
0 0 5 2
20 20
27 -14
0 16
-7 -9
23 38
22 24
3 0
Sample Output1
52
【样例说明】
泽泽（20，20）传给3号队员（0，16），3号队员再射门（0，0），总共用了52。
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u252
【题解】
直接三层fou循环枚举两个人之间能不能传球;
i,j枚举要传球的两个人,k枚举“挡在中间的人”,如果i,k的距离s1加上j,k的距离s2等于i,j的距离s3;则k的确挡在了i,j之间，则不建边；否则建一条边；(边权就是i,j的距离);
然后n个人再分别建一条指向球门的边即可;
最后从泽泽的1号节点开始做最短路；(球门就当做0号节点)
最后输出f[0];
【完整代码】
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 400;
struct point
{
double x,y;
};
vector <int> a[MAXN];
vector <double> w[MAXN];
queue <int> dl;
bool inque[MAXN];
double a0,b0;
int n,m;
point b[400],c[MAXN],goal;
double f[MAXN];
double sqr(double x)
{
return x*x;
}
double dis(point a,point b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
double jue(double x)
{
if (x>0)
return x;
else
return -x;
}
bool can(point a,point b,point c)
{
double dis1 = dis(a,b);
double dis2 = dis(b,c);
double dis3 = dis(a,c);
dis1 = dis1+dis2;
double judge =jue(dis1-dis3);
if (judge<1e-4)
return false;
else
return true;
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
scanf("%lf%lf%d%d",&goal.x,&goal.y,&n,&m);
for (int i = 1;i <= n;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
for (int i = 1;i <= m;i++)
scanf("%lf%lf",&c[i].x,&c[i].y);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i!=j)
{
bool ok = true;
for (int k =1;k <= m;k++)
if (!can(b[i],c[k],b[j]))
{
ok = false;
break;
}
if (ok)
{
a[i].push_back(j);
w[i].push_back(dis(b[i],b[j]));
}
}
for (int i = 1;i <= n;i++)
{
a[i].push_back(0);
w[i].push_back(2*dis(b[i],goal));
}
for (int i = 0;i <= n;i++)
f[i] = 2100000000.0;
f[1] = 0;
dl.push(1);
inque[1] = true;
while (!dl.empty())
{
int x = dl.front();
inque[x] = false;
dl.pop();
int len = a[x].size();
for (int i = 0;i <= len-1;i++)
{
int y = a[x][i];
double c = w[x][i];
if (f[y]>f[x]+c)
{
f[y] = f[x] + c;
if (!inque[y])
{
inque[y] = true;
dl.push(y);
}
}
}
}
printf("%.0lf
",f[0]);
return 0;
}