HDU 1033 Edge：折紙展開曲線繪製

問題描述

一張長方形紙只沿短邊平行線折疊，每次折疊方向為 'A'（頂面合）或 'V'（底面合）。展開後看長邊形成折線，輸入折疊序列（如 "AVV"），輸出 PostScript 繪圖命令：起始 (300,420) moveto，第一轉折點 (310,420) lineto，後續每段長 10，按序列轉向（A 順時針，V 逆時針），最後 stroke showpage。

解題思路

模擬折疊展開：初始方向向右 (1,0)。每個字符對應 90 度轉向：'A' 為右轉（順時針），方向向量 (dx,dy) → (dy, -dx)；'V' 為左轉（逆時針），(dx,dy) → (-dy, dx)。從 (300,420) 起，先輸出 moveto，再輸出第一段終點 (310,420) lineto，然後按序列依次轉向並輸出下一點。最後輸出 stroke showpage。

代碼實現 (C++)

#include 
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        cout << "300 420 moveto\n";
        cout << "310 420 lineto\n";
        int x = 310, y = 420;
        int dx = 1, dy = 0; // 向右
        for (char c : s) {
            if (c == 'A') { // 右轉
                int ndx = dy, ndy = -dx;
                dx = ndx; dy = ndy;
            } else { // 'V' 左轉
                int ndx = -dy, ndy = dx;
                dx = ndx; dy = ndy;
            }
            x += 10 * dx;
            y += 10 * dy;
            cout << x << " " << y << " lineto\n";
        }
        cout << "stroke\nshowpage\n";
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(len)。
• 空間複雜度：O(1)。

總結

折紙展開幾何模擬，方向向量旋轉 90 度即可。PostScript 命令格式固定，注意輸出換行與空格。