地址连接:http://www.karrels.org/Ed/ACM/96/ccorners.html
刚开始做这题时候，没作对，后来优化了下代码，问了下pozen，测试代码通过，只是没有地方提交。。。
寻路是dp(动态规划)。。其实可以成优化成很小，直接是求所有点中的其中2点距离。
1996 ACM Scholastic Programming Contest Finals
sponsored by Microsoft ®
Problem C
Cutting Corners
Input file: corner.in
代码如下：
1
# include <iostream>
2# include <cmath>
3using namespace std;
4
5#define MAXRECT 22
6
7struct Point
8
{
9
double x,y;
10 bool operator == (Point & r)
11
{
12 return (x==r.x && y==r.y);
13
}
14
};
15
16struct Rect
17{
18 Point p[4];
19};
20
21Point reg[4*MAXRECT+2]; // 最多可能出现的点,包括起点和终点
22Rect rect[MAXRECT]; // 矩形
23double arr_point[4*MAXRECT+2][4*MAXRECT+2]; // 枚举所有点之间的距离
24int Count = 0;
25
26
27double disten(Point a , Point b)
28{
29 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
30}
31// 判断线段是否相交
32bool IsLineSegmentCross(Point pFirst1, Point pFirst2, Point pSecond1, Point pSecond2)
33{
34 //每个线段的两点都在另一个线段的左右不同侧，则能断定线段相交
35 //公式对于向量(x1,y1)->(x2,y2),判断点(x3,y3)在向量的左边,右边,还是线上.
36 //p=x1(y3-y2)+x2(y1-y3)+x3(y2-y1).p<0 左侧, p=0 线上, p>0 右侧
37 if(pFirst1 == pSecond1 || pSecond2 == pFirst1)
38 return false;
39 if(pFirst2 == pSecond1 || pSecond2 == pFirst2)
40 return false;
41 long Linep1,Linep2;
42 //判断pSecond1和pSecond2是否在pFirst1->pFirst2两侧
43 Linep1 = pFirst1.x * (pSecond1.y - pFirst2.y) +pFirst2.x * (pFirst1.y - pSecond1.y) + pSecond1.x *
44
45(pFirst2.y - pFirst1.y);
46 Linep2 = pFirst1.x * (pSecond2.y - pFirst2.y) + pFirst2.x * (pFirst1.y - pSecond2.y)+ pSecond2.x *
47
48(pFirst2.y - pFirst1.y);
49 if ( ((Linep1 ^ Linep2) >= 0 ) && !(Linep1==0 && Linep2==0))//符号位异或为0:pSecond1和pSecond2在pFirst1-
50
51>pFirst2同侧
52 {
53 return false;
54 }
55 //判断pFirst1和pFirst2是否在pSecond1->pSecond2两侧
56 Linep1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
57 pSecond2.x * (pSecond1.y - pFirst1.y) +
58 pFirst1.x * (pSecond2.y - pSecond1.y);
59 Linep2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
60 pSecond2.x * (pSecond1.y - pFirst2.y) +
61 pFirst2.x * (pSecond2.y - pSecond1.y);
62 if ( ((Linep1 ^ Linep2) >= 0 ) && !(Linep1==0 && Linep2==0))//符号位异或为0:pFirst1和pFirst2在pSecond1-
63
64>pSecond2同侧
65 {
66 return false;
67 }
68 //否则判为相交
69 return true;
70}
71
72bool Piont2_in_Rcet(Point a, Point b , Rect c)// 点a,b是否经过矩形c
73{
74 for(int i = 0 ; i < 4 ; i++)
75 {
76 if(IsLineSegmentCross(a,b,c.p[i%4],c.p[(i+1)%4]))
77 return true;
78 }
79 return false; // 不再矩形中
80}
81
82// 求出所有顶点之间的距离
83void find_path()
84{
85 for(int i = 0; i < Count-1 ; i++)
86 {
87 for(int j = i+1 ; j < Count ; j++)
88 {
89 int flag = 0;
90 for(int k = 0 ; k < 4 ; k++)
91 {
92 if(Piont2_in_Rcet(reg[i],reg[j],rect[k]))
93 {
94 arr_point[i][j] = -1;
95 flag = 1;
96 break;
97 }
98 }
99 if(!flag)
100 {
101 arr_point[j][i] = arr_point[i][j] = disten(reg[i],reg[j]);
102
103 }
104 }
105 }
106}
107
108// dp (n^3) 求解
109void GetShortest()
110{
111 for (int i = 0 ; i < Count ; i++)
112 {
113 for (int j = 0 ; j < Count ; j++)
114 {
115 for (int k = 0 ; k < Count ; k++ )
116 {
117 if( (arr_point[i][j] !=-1) && arr_point[j][k] !=-1 && (arr_point[i][k]==-1 ||
118
119arr_point[i][k] > (arr_point[i][j]+arr_point[j][k])))
120 {
121 // if(i==0)
122 // cout <<"i =" <<i <<" j = "<< j <<" k="<<k<<" len = "<<arr_point[i][k]<<endl;
123 arr_point[i][k] = arr_point[i][j] + arr_point[j][k];
124 }
125 }
126 }
127 }
128}
129int main()
130{
131
132 //freopen("corner.in","r",stdin);
133 int n,i,j;
134 double a,b,c,d,e,f;
135 int m = 1;
136 while (cin >> n && n != -1)
137 {
138 memset(reg,0,sizeof(reg));
139 memset(rect,0,sizeof(rect));
140 cin >> reg[0].x >> reg[0].y >> reg[1].x >> reg[1].y;
141 Count = 2;
142 int index = 2;
143 for(i = 0 ; i < n ; i++)
144 {
145 cin >> a >> b >> c >> d >> e >>f;
146 reg[index].x = rect[i].p[0].x = a;
147 reg[index].y = rect[i].p[0].y = b;
148 reg[1+index].x = rect[i].p[1].x = c;
149 reg[1+index].y = rect[i].p[1].y = d;
150 reg[2+index].x = rect[i].p[2].x = e;
151 reg[2+index].y = rect[i].p[2].y = f; // 4个矩形赋值
152
153 reg[index+3].x = rect[i].p[3].x = a+e - c; // 根据对称性
154 reg[index+3].y = rect[i].p[3].y = b+f - d;
155
156 index +=4;
157 Count +=4;
158 } // 读取数据
159
160
161 for(i = 0 ; i < 4*MAXRECT+2 ; i++)
162 for(j = 0 ; j < 4*MAXRECT+2 ; j++)
163 arr_point[i][j] = -1; // 任意2点不可达到
164
165
166 find_path();
167 GetShortest();
168 //cout << "route distance: " << arr_point[0][1] <<endl;
169 printf("Scenario #%d\n route distance: %.2f\n",m++,arr_point[0][1]);
170 }
171 return 0;
172}
173