首页 > ACM题库 > HDU-杭电 > HDU 3272-Mission Impossible[解题报告]HOJ
2014
03-13

HDU 3272-Mission Impossible[解题报告]HOJ

Mission Impossible

问题描述 :

There are A, B, C, D four kinds of resources, A can be obtained at any point in the X-axis. B can be obtained at any point in the Y-axis. C and D each will only be able to achieve at a certain point. Giving the coordinates of C and D, the coordinates of your current location. Find the shortest path to obtain the four kinds of resources and go back.

输入:

The first line contains the number T of test cases(T<=150). Each of the following T lines consists of six integers cx, cy, dx, dy, hx and hy. (cx, cy) is the coordinates of resource C, (dx, dy) is the coordinates of resource D, (hx, hy) is the coordinates of your current location.
All the numbers of the input are in the range [-1000, 1000].

输出:

The first line contains the number T of test cases(T<=150). Each of the following T lines consists of six integers cx, cy, dx, dy, hx and hy. (cx, cy) is the coordinates of resource C, (dx, dy) is the coordinates of resource D, (hx, hy) is the coordinates of your current location.
All the numbers of the input are in the range [-1000, 1000].

样例输入:

3
1 1 2 2 3 3
1 1 -1 -1 -1 -1
1 -1 1 1 -1 1

样例输出:

8.49
5.66
6.83

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct point {
 double x,y;
}p[10];
#define sqr(x) ((x)*(x))
double dist(int i,int j){
 return sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y));
}
double calc(int i,int j,int k){
 if (j==3){
 if (p[i].y*p[k].y<=0){
 return dist(i,k);
 }else {
 p[4] = p[i];
 p[4].y*=-1;
 return dist(4,k);
 }
 }else {
 if (p[i].x*p[k].x<=0){
 return dist(i,k);
 }else {
 p[4] = p[i];
 p[4].x*=-1;
 return dist(4,k);
 }
 }
}
double calcmove(int i,int j,bool dx,bool dy){
 p[4] = p[j];
 if (dx) p[4].y*=-1;
 if (dy) p[4].x*=-1;
 return dist(4,i);
}
int order[10];
int main(){
 int tt,i,j,k;
 scanf("%d",&tt);
 while(tt--){
 for (i=0;i<3;i++)
 scanf("%lf%lf",&p[i].x,&p[i].y);
 p[3].x=p[3].y = 0;
 order[1] = 0,order[2] = 1,order[3] = 3,order[4] =4;
 order[0] = order[5] = 2;
 double ans = 1e20;
 do{
 
 int now = 0;
 double tmp = 0;
 while(now<5){
 if (order[now+1]>=3){
 if (order[now+2]>=3){
 point a = p[order[now]],b = p[order[now+3]];
 bool dx = 0,dy = 0;
 if (a.y*b.y>0) dx = 1;
 if (a.x*b.x>0) dy = 1;
 tmp+=calcmove(order[now],order[now+3],dx,dy);
 now+=3;
 }
 else {
 tmp+=calc(order[now],order[now+1],order[now+2]);
 now+=2;
 }
 }else {
 tmp+=dist(order[now],order[now+1]);
 now++;
 }
 }
 if (tmp<ans) ans = tmp;
 }while(next_permutation(order+1,order+5));
 printf("%.2lf\n",ans); 
 }
}

  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。