[TimusACM][1258]程序員撞牆的問題，timusacm1258

[TimusACM][1258]程序員撞牆的問題，timusacm1258

（本文是從我的舊博客遷移過來的）

問題地址：http://acm.timus.ru/problem.aspx?space=1&num=1258

　　前幾日在博客園看到這種在線測試的時候，有一種相見恨晚的感覺，於是隨便選了一道感興趣的題（No.1258：Pool）開始做。為了准確了解題的意思，我把題翻譯成中文了，這道題的原理和台球很相似（由於以前常玩可樂8，所以對台球的問題倍感親切）。但不知道為什麼出題人將台球問題說成了一個程序員撞牆的問題。下面是我翻譯後的，英語不好，譯錯的地方請見諒。

  

問題：

 

1258. Pool

運行時間限制: 1.0 秒
內存限制: 16 MB   在午休的時候，程序員Vasechkin喜歡在他的矩形房間裡閒逛。他從他工作的地方開始溜達，直到他有了再開始工作的念頭才停止。我們已知當Vasechkin撞牆時，他的運動規律相當符合“入射角等於反射角”定律。並且Vasechkin走的路線是很直的線段。凶狠的辦公室主任決定找出他浪費了多少時間在溜達上。顯然Vasechkin走過的長度除以他的平均速度（事先測量）可得出所用的時間。所以必須知道這個長度!並且從Vasechkin的碰撞中能清楚的知道Vasechin的撞牆順序。可能還有更簡單的方法計算出程序員所浪費的時間，但是辦公室主任認為這是解決問題的最佳方法。

輸入

第一行由兩個整數W和D組成——他們分別是Vasechkin所在房間的寬和長（0<=W,D<=1000，單位：米）。
第二行由Vasechkin的起始位置相對於左上角的坐標組成（0<X0<W，0<y0<D）。 
第三行是終點相對於左上角的坐標（0<x1<W,0<y1<D），
最後的第四行由字母L，R，F，B組成，每個字母分別代表Vasechkin撞牆的順序——左，右，上，下。
撞牆的次數不超過1000.
這個程序員永遠不會撞在牆角，並且他的起始位置不會貼在牆上。

輸出

Vasechkin從起點到終點所走的長度，保留小數點後四位。

例子

inputoutput

            10 20
            9 1
            1 19
            FLRLRB

52.8015

  出題人: Pavel Egorov
題來源: 2003年10月11日斯維爾德洛夫斯克州大學生編程公開賽

==============================================================

簡單理解就是：給長寬，起點和終點，撞邊的情況，最後求的是軌跡的長度。
按下圖，做輔助圖後，可以比較容易的根據勾股定理求出斜邊。


X0,X1,Y0,Y1,W,D這些都是已知的，接下來就是分析碰撞順序與這些量的關系。

X方向的位移和Y方向的可以分別分析。
X方向的位移規律找出來了，Y方向的位移也是一樣的。
不撞牆時：(X0-X1)^2和(X1-X0)^2是一樣的，為了跟下面統一，所以把X0寫在前面


再分析一下系數的規律：


規律已經比較明顯：
X0的系數規律——先往左的時候為正1，先往右的時候為負1。
X1的系數規律——碰撞次數為偶數的時候與X0系數異號，奇數時同號。
W的系數規律——R個數乘以2。

Y方向的規律也是如此。

分析到此，已經可以在程序裡面方便的實現這些邏輯了。

下面是我寫的代碼，如果按照正確格式輸入，結果是正確的。
但不知道為什麼，提交到ACM系統中報錯，也不知道錯誤是什麼，調試不了，我已經是激情殆盡了。哪位朋友如果運行成功了或者發現錯誤了，一定要告訴我下。
有一個問題，題中要求結果保留4位小數，但我沒看出來是“四捨五入”還是“直接捨去”，但我兩種都試了，都說答案有誤。

下面是代碼：

 1 using System;
 2 namespace ACM1258
 3 {
 4     class Program
 5     {
 6         static void Main()
 7         {
 8             System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
 9             
10             double result;    //輸出
11             double sideX, sideY;   //兩個直角邊
12             double X0,X1,Y0,Y1,W,D;   //各個參數
13             string flrb;    //撞牆順序
14             int coeffX0=0,coeffX1=0,coeffY0=0,coeffY1=0,coeffW=0,coeffD=0;  //各個系數
15             bool checkLorR= true,checkForB= true;  //是否檢查第一個LR、FB
16             bool LFirst= false,FFirst= false;      //判斷第一個撞哪邊
17             bool FBpair= true,LRpair=true;         //F與B、L與R的個數是否相等；
18 
19             string[] temp;
20             temp = Console.ReadLine().Split();               //[0]:W   [1]:D
21             W=Convert.ToDouble(temp[0]);
22             D=Convert.ToDouble(temp[1]);
23             temp = Console.ReadLine().Split();              //[0]:X0  [1]:Y0
24             X0=Convert.ToDouble(temp[0]);
25             Y0=Convert.ToDouble(temp[1]);
26             temp = Console.ReadLine().Split();               //[0]:X1  [1]:Y1
27             X1=Convert.ToDouble(temp[0]);
28             Y1=Convert.ToDouble(temp[1]);
29             flrb = Console.ReadLine();
30             
31             for (int i = 0; i < flrb.Length; i++)
32             {
33                 switch (flrb[i])
34                 {
35                     case 'F':
36                         if (checkForB)
37                         {
38                             FFirst = true;
39                             checkForB = false;
40                         }
41                         FBpair = !FBpair;
42                         break;
43                     case 'L':
44                         if (checkLorR)
45                         {
46                             LFirst = true;
47                             checkLorR = false;
48                         }
49                         LRpair = !LRpair;
50                         break;
51                     case 'R':
52                         if (checkLorR)
53                         {
54                             LFirst = false;
55                             checkLorR = false;
56                         }
57                         LRpair = !LRpair;
58                         coeffW++;
59                         break;
60                     case 'B':
61                         if (checkForB)
62                         {
63                             FFirst = false;
64                             checkForB = false;
65                         }
66                         FBpair = !FBpair;
67                         coeffD++;
68                         break;
69                     default:
70                         break;
71                 }
72             }
73 
74             coeffX0 = LFirst ? 1 : -1;
75             coeffX1 = LRpair ? -coeffX0 : coeffX0;
76             coeffY0 = FFirst ? 1 : -1;
77             coeffY1 = FBpair ? -coeffY0 : coeffY0;
78 
79             sideX = (coeffX0 * X0 + coeffX1 * X1) + coeffW * 2 * W;
80             sideY = (coeffY0 * Y0 + coeffY1 * Y1) + coeffD * 2 * D;
81             
82             result = Math.Sqrt(sideX*sideX+sideY*sideY);
83             //result = ((int)(result * 10000)) / 10000.0;   //這是直接捨去的，否則就是四捨五入
84             Console.WriteLine(result.ToString("F4"));
85         }
86     }
87 }

 

運行題中的測試用例結果：