Solve

NOIP2001Car的旅行路线

题目解答

新年第一题：这道题目很值得一说，首先这是一个比较典型的计算几何转化为图论去做，同时也是需要结合两者的不错的题目。大体思想是首先用向量法计算出第4个点，因为第4个点是现有的3个点中的作为现有RT三角形的一个对角点，所以先要确定直角点，用点积为0判定，剩下的很简单了。接着要建模为一张图，然后计算最短路径。大体就是这样。

关于计算最短路径：我的想法是先求出所有点对的最短路径，然后遍历A市与B市的飞机场选出一个最短的，但是这样似乎麻烦而且时效低，所以我介绍一下官方的强大方法：首先对于A市和B市，把他们的铁路价格都改为0，这样无论选择两个城市中的哪个机场，都不用额外花费铁路价格，把城市封装为一个整体，意味着A、B的机场任意。做一遍Dijkstra即可。

运行情况

NOIP 2001

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<iomanip>
#include<cmath>
#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;
const int Max=500;
const double MAX = 99999999.9;
struct node{ //存一个完整的矩形 
    double pos[5][2];
}rect[Max];
struct Node{ //存储飞机场
     double x,y;
    int mark;
    double val;
}plane[4*Max];
double dis[4*Max],val[Max],t;
int n,s,A,B,now,now2,A1,B1;
bool vis[4*Max];
inline double compute(node rect,int a,int b,int c){ //计算点积 
    double x1,y1,x2,y2;
    x1=rect.pos[a][0]-rect.pos[c][0];
    y1=rect.pos[a][1]-rect.pos[c][1];
    x2=rect.pos[b][0]-rect.pos[c][0];
    y2=rect.pos[b][1]-rect.pos[c][1];
    return x1*x2+y1*y2;
}
inline void cal(node &rect,int a,int b,int c){ //计算第4个点
    rect.pos[4][0]=rect.pos[a][0]+rect.pos[b][0]-rect.pos[c][0];
    rect.pos[4][1]=rect.pos[a][1]+rect.pos[b][1]-rect.pos[c][1];
}
inline void the4th(node &rect){ //枚举直角点 
    if(compute(rect,1,3,2)==0){
        cal(rect,1,3,2);
        return;}
    if(compute(rect,2,3,1)==0){
        cal(rect,2,3,1);
        return;}
    if(compute(rect,2,1,3)==0){
        cal(rect,2,1,3);
        return;}
}
inline double dist(Node a,Node b){ //计算距离 
    double len=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    if(a.mark==b.mark){
       if(a.mark==A1 || a.mark==B1) return 0;//important
       return len*a.val;
     }
    return len*t;
}
int main(){
    cin>>n>>s>>t>>A>>B;
    A1=A;B1=B;
    for(int i=1;i<=s;i++) dis[i]=MAX;
    for(int i=1;i<=s;i++){
        for(int j=1;j<=3;j++) cin>>rect[i].pos[j][0]>>rect[i].pos[j][1];
        the4th(rect[i]);
        cin>>val[i];
        for(int k=1;k<=4;k++){ //建成图
            plane[4*(i-1)+k].x=rect[i].pos[k][0]; 
            plane[4*(i-1)+k].y=rect[i].pos[k][1];
            plane[4*(i-1)+k].mark=i; //标记属于哪个城市
            plane[4*(i-1)+k].val=val[i]; // 铁路费用
        }
    }
    A*=4;B*=4; //选择 A,B市的最后一个点
    for(int i=1;i<=4*s;i++) //dijkstra
        dis[i]=dist(plane[i],plane[A]);
    do{
        double MIN=MAX;
        now=0;
        for(int i=1;i<=s*4;i++)
            if(!vis[i] && MIN>dis[i]){
                MIN=dis[i];
                now=i;
            }
        if(now!=0){
            vis[now]=true;
            for(int i=1;i<=s*4;i++)
                if(!vis[i]) dis[i]=Min(dis[i],dis[now]+dist(plane[now],plane[i]));
        }
    }while(now!=0);
    cout<<setiosflags(ios::fixed)<<setprecision(1)<<dis[B]<<endl;
    return 0;
}

难易等级

Middle Up(Noip the 4th)