1. 泽泽在巴西
题目ID：1379必做题100分
最新提交：Wrong Answer 30 分
历史最高：Wrong Answer 30 分
时间限制: 1000ms 空间限制: 65536kB
题目描述
泽泽帮助了英国某街道尽量减少酸雨的伤害，街道办主任非常感激他，就把他领到一扇门前，告诉他这扇门能通往好地方，具体好到什么程度要看泽泽人品。泽泽毫不犹豫地走了进去……
泽泽来到了足球王国——巴西。这可是个好地方，泽泽看来人品攒了不少了。这里大街小巷都在踢足球，其乐无穷。
突然，泽泽被一个人拎了起来，一看，是个足球流氓。他后面跟了一大群足球流氓，正虎视眈眈地看他。他们要求和泽泽比赛，输了就要揍他。
没办法，泽泽硬着头皮和足球流氓另外掳来的几个人一起组建了一只队伍，和足球流氓队比赛。
比赛开始，泽泽队率先发球。泽泽观察了四周，想怎么才能用最短的时间射门呢？
射门的时间为距离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个人坐标相同。
输出格式：
输出一个整数，是最短时间四舍五入取整后的结果。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n,m,ans;
double dis[N][N];
struct point{
int x,y;
}a[N],b[N];
bool check(point a,point b,point c){
if((b.x-a.x)*(c.y-a.y)==(b.y-a.y)*(c.x-a.x)){
if(min(a.x,b.x)<=c.x&&max(a.x,b.x)>=c.x&&min(a.y,b.y)<=c.y&&max(a.y,b.y)>=c.y)return 0;
return 1;
}
return 1;
}
int main(){
cin>>a[n+1].x>>a[n+1].y>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
for(int i=1;i<=m;i++)cin>>b[i].x>>b[i].y;
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++){
if(i==j)continue;
bool flag=1;
for(int k=1;k<=m;k++){
if(!check(a[i],a[j],b[k])) {
flag=0;
break;
}
}
if(flag){
dis[i][j]=sqrt(pow(a[j].x-a[i].x,2)+pow(a[j].y-a[i].y,2));
if(i==n+1||j==n+1)dis[i][j]*=2;
} else dis[i][j]=1e9;
}
}
for(int k=1;k<=n+1;k++){
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++){
if(i==j)continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
printf("%.0lf",dis[1][n+1]);
}