题目描述 泽泽帮助了英国某街道尽量减少酸雨的伤害，街道办主任非常感激他，就把他领到一扇门前，告诉他这扇门能通往好地方，具体好到什么程度要看泽泽人品。泽泽毫不犹豫地走了进去…… 泽泽来到了足球王国——巴西。这可是个好地方，泽泽看来人品攒了不少了。这里大街小巷都在踢足球，其乐无穷。 突然，泽泽被一个人拎了起来，一看，是个足球流氓。他后面跟了一大群足球流氓，正虎视眈眈地看他。他们要求和泽泽比赛，输了就要揍他。 没办法，泽泽硬着头皮和足球流氓另外掳来的几个人一起组建了一只队伍，和足球流氓队比赛。 比赛开始，泽泽队率先发球。泽泽观察了四周，想怎么才能用最短的时间射门呢？ 射门的时间为距离*2，而传球的时间是距离*1。所以泽泽想找一条用时最少的射门路径，来打败足球流氓。 足球流氓当然不会袖手旁观，他们会拦截。当泽泽队伍中的传球人、被传球人之间有某足球流氓并且他们在同一直线上时，传球不会成功，即不能这样传球。比如A（1，2）想传球给B（7，8），中间有个足球流氓C（3，4），则他们在同一直线，传球不成功。射门不受足球流氓影响。
分析 好难啊，都不想写题解了。。。 floyed人人都会，就说一下判断足球流氓拦截吧：首先要判断足球流氓是否在队友和队友形成的矩阵之间： 然后叉积： P1=(X1,Y1),P2=(X2,Y2),P0=(X0,Y0) m=(x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) 如果m等于0那么这三点就在一条直线上了！ 还有射门的距离要*2（这个非常重要！）
【代码可能有些地方很繁琐，没办法，安全起见】
#include <iostream> #include <cstdio> #include <cmath> #include <memory.h> using namespace std; int n,m,i,j,k,a[401][401]; float f[401][401]; float min(float a,float b) { if (a<b) return a; else return b; } bool tf(float x1,float y1,float x2,float y2,float x3,float y3) { if ((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)!=0) return true; if (sqrt(pow(x1-x2,2)+pow(y1-y2,2))<sqrt(pow(x1-x3,2)+pow(y1-y3,2))|| sqrt(pow(x1-x2,2)+pow(y1-y2,2))<sqrt(pow(x2-x3,2)+pow(y2-y3,2))) return true; return false; } int main() { float o; freopen("brazil.in","r",stdin); freopen("brazil.out","w",stdout); memset(f,100,sizeof(f)); scanf("%d%d%d%d",&a[0][1],&a[0][2],&n,&m); for (i=1;i<=n+m;i++) scanf("%d%d",&a[i][1],&a[i][2]); for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) for (k=n+1;k<=n+m;k++) if (i!=j&&i!=k&&tf(a[i][1],a[i][2],a[j][1],a[j][2],a[k][1],a[k][2])) { o=pow((float) a[i][1]-a[j][1],2)+pow((float)a[i][2]-a[j][2],2); f[i][j]=sqrt(o); f[j][i]=f[i][j]; } for (i=1;i<=n;i++) { o=pow((float)a[i][1]-a[0][1],2)+pow((float)a[i][2]-a[0][2],2); f[i][0]=sqrt(o)*2; f[0][i]=f[i][0]; } for (i=0;i<=n;i++) for (j=0;j<=n;j++) for (k=0;k<=n;k++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); printf("%.f",f[0][1]); return 0; }