[模拟] UVa177 折纸痕（点，线的绕点旋转）

题目

思路

1. 本题的思路其实通过观察图形，很容易想出来的。即维护两个点s和rot，每次将整个图形绕rot点顺时针选择90度，并将rot点更新为旋转后的s点即可。
2. 关键在于横竖线的表达与数据结构问题。陈锋所采用的方法是：用start, end, vertical来描述一条线，随后对线的操作即为对start, end两个点的操作，以及极其重要的normalize函数。
3. 对于平面几何点绕点旋转的方法：
   
   • 点p，以点r为中心，顺时针旋转90度

pv = p - r;  //以r为中心，建立相对坐标系
p' = Point(pv.y, -pv.x);
p' += r;   //相对坐标系用完，还原

• 点p，以点r为中心，逆时针旋转90度

pv = p - r;
p' = Point(-pv.y, pv.x);
p' += r;

4.代码的输出，实现了由线到点的转化，还是值得看一看的，这类横线竖线的问题UVA上有很多。
5.陈锋大佬代码中，对于各种数据结构的声明和运用，能让代码更易读，debug起来也方便，应该学习。

代码

// Paper Folding, UVa177
// 陈锋，侵删
#include <cassert>
#include <algorithm>
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#define _for(i,a,b) for( int i=(a); i<(b); ++i)

using namespace std;

struct Point {
  int x, y;
  Point(int x=0, int y=0):x(x),y(y) {}
};
typedef Point Vector;

Vector operator+ (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator- (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator* (const Vector& A, int p) { return Vector(A.x*p, A.y*p); }
bool operator== (const Point& a, const Point &b) { return a.x == b.x && a.y == b.y; }
bool operator!= (const Point& a, const Point &b) { return !(a==b); }
bool operator< (const Point& p1, const Point& p2) { return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); }
ostream& operator<<(ostream& os, const Point& p) { 
    return os<<p.x<<','<<p.y;
}

// p围绕r顺时针旋转90度，返回旋转后的点
Point rotate(const Point& p, const Point& r) {
    Vector pv = p - r;
    Point ans = r + Vector(pv.y, -pv.x);
    return ans;
}

const int MAXN = 13;
struct Line {
    Point start, end;
    bool vertical;

    // 围绕r顺时针旋转90度
    Line rotate(const Point& r) {
        Line ret;
        ret.start = ::rotate(start, r);
        ret.end = ::rotate(end, r);
        return ret;
    }
    // 规整，保证start在end的左边或者上边
    void normalize() {
        assert(start != end);
        assert(start.x == end.x || start.y == end.y);
        vertical = (start.x == end.x);
        if(vertical) {
            if(start.y > end.y) swap(start.y, end.y);
        } else {
            if(start.x > end.x) swap(start.x, end.x);
        }
    }
};

int n, LineCnt;
vector<Line> lines;

int main()
{    
    lines.reserve(1<<MAXN);
    while(cin>>n&&n) {
        Line l;
        l.end = Point(1, 0);
        l.vertical = false;
        lines.clear();
        lines.push_back(l);
        int maxY = l.start.y, minY = l.start.y,
            minX = l.start.x, maxX = l.end.x;

        Point s = l.start, rot = l.end;
        _for(i, 0, n) {
            int sz = lines.size();            
            _for(j, 0, sz) {
                Line nl = lines[j].rotate(rot);
                nl.normalize();
                lines.push_back(nl);
            }
            rot = rotate(s, rot);
        }

        map<Point, char> pc;
        for(auto& l : lines) {
            Point& lp = l.start;
            lp.x *= 2;
            if(l.vertical) lp.x--;
            minX = min(lp.x, minX);
            maxX = max(lp.x, maxX);
            minY = min(lp.y, minY);
            maxY = max(lp.y, maxY);
            pc[lp] = l.vertical ? '|' : '_';
        }

        // cout<<"minX = "<<minX<<endl;
        string buf;
        for(int y = maxY; y >= minY; y--) {
            buf.clear();
            for(int x = minX; x <= maxX; x++) {
                Point p(x,y);
                if(pc.count(p)) buf += pc[p];
                else buf += ' ';
            }
            while(*(buf.rbegin()) == ' ') buf.erase(buf.size()-1);
            cout<<buf<<endl;
        }

        cout<<"^"<<endl;
    }
    return 0;
}