題目 官解

這是今年的第四名國手懲罰 (?) 之一 (QQ)，所以我就來寫這個題目了。

題目大意

給一個由 L 和 P 構成的長度 $n$ 的字串 $S$，請構造一個簡單 $n$ 邊形，滿足它的邊都和 x 或 y 軸平行、相鄰邊互相垂直，並且存在邊上的一點，滿足從那個點開始逆時針繞這個多邊形一圈，轉彎的方向順序和 $S$ 所表示的相同。在 $S$ 中，L 代表左轉，P 代表右轉。

題解

首先要先判斷怎樣的狀況有解。既然是繞一圈，就代表你剛好轉了一個周角，也就是 L 的數量減 P 的數量要恰好是 4。

如果把 L 當左括號、P 當右括號的話，$S$ 會是一個有四個左括號找不到配對的環狀括號字串，先把它們找出來。因為一對 L、P 剛好會讓方向變回本來的方向，所以一個有效的括號字串是不會改變方向的，由此可知那四個沒人配對的 L 就會像是四邊形的四個角，剩下的部分會被它們切成四段，等同於四邊形的四個邊。

現在我們要做的事情就是：對一個有效的括號字串，構出一條邊來。舉例來說，範測 LLLLPPLL 中沒有人配的 L 就是前兩個和後兩個，中間的 LLPP 是其中一條邊，它可以長成這個樣子：

先把最高層級的括號分開來，例如 (())(()())() 就是 (())、(()())、()，然後對每一組分開處理，最後再直接接起來就好了。所以接下來要處理 (...) 裡面的部分，我的做法是每一對 () 都會佔據一個正方形，裡面有很多小正方形，每個小正方形就是下一層級的括號，裡面再遞迴處理。邊長的話是小正方形的邊長總和再 +2。

像是這樣，這一組括號會從正方形的左下開始、右上結束，然後小正方形的部分就是把它單獨構完後轉 90 度。至於長度的部分，A 和 D 都是邊長減 1，B 和 C 是 1，然後可以發現到每一邊都有長度是 1 的空隙，那是避免有邊黏在一起用的。

然後把同一個邊上的每一組括號構完再串起來就做好一條邊，把四條邊做完後還要想辦法把它們串起來，最簡單的方式就是把四個邊弄超長，然後把剛剛構的部分放中間，這樣就不怕中間轉來轉去的部分相撞了。

成品，輸入是 LLLPPLLLPLPPLLPL：

Code

視覺化工具：

from matplotlib import pyplot as plt

n = int(input()) # 點的數量

lst = [int(t) for t in input().split(' ')]
fp = lst

for i in range(0, n):
    x, y = [int(t) for t in input().split(' ')]

    plt.plot([lst[0], x], [lst[1], y], '.-', c='blue')
    lst = (x, y)
plt.plot([lst[0], fp[0]], [lst[1], fp[1]], '.-', c='blue')

plt.show()

AC Code:

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 1e7; // 接在每一條邊頭尾的長度，debug 的時候可以調小一點，會比較好看

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

pii operator+(pii a, pii b){
    return mp(a.F + b.F, a.S + b.S);
}

pii operator-(pii a, pii b){
    return mp(a.F - b.F, a.S - b.S);
}

pii operator+=(pii& a, pii b){
    return a = a + b;
}

pii operator*(pii a, int b){
    return mp(a.F * b, a.S * b);
}

pii operator-(pii a){
    return mp(-a.F, -a.S);
}

vector<pii> ans;
pii now = mp(0, 0);

void move(pii v, int d){
    d %= 4;
    if(d == 0) now += v;
    else if(d == 1) now += mp(-v.S, v.F);
    else if(d == 2) now += -v;
    else now += mp(v.S, -v.F);
    ans.eb(now);
}

void move(pii to){
    ans.eb(to);
    now = to;
}

int type(pii seg){
    if(seg.F == 0) return 1;
    return 0;
}

struct block{
    int w = 0, h = 0;
    vector<block*> nxt;
    void add(block* b){
        w += b->h;
        h += b->w;
        nxt.eb(b);
    }
};

int lp = 0;
string s;
block* solve(){
    block* b = new block({2, 2});
    lp++;
    while(s[lp] == 'L'){
        b->add(solve());
    }
    lp++;
    return b;
}

void draw(block* b, int dir){
    move(mp(b->w - 1, 0), dir);
    move(mp(0, 1), dir);
    for(block* nxt : b->nxt){
        draw(nxt, dir + 1);
    }
    move(mp(0, 1), dir);
    move(mp(b->w - 1, 0), dir);
}

int main(){
    StarBurstStream;

    string t;
    cin >> t;
    int n = t.size();

    int cnt = 0;
    for(char i : t){
        if(i == 'L') cnt++;
        else cnt--;
    }

    if(cnt != 4){
        cout << "NIE\n";
        return 0;
    }

    deque<pii> st;
    for(int i = 0; i < n; i++){
        if(t[i] == 'L'){
            st.eb(mp(i, 1));
            continue;
        }
        if(!st.empty() && st.back().S == 1){
            st.pob;
            continue;
        }
        st.eb(mp(i, -1));
    }
    while(st.front().S == -1){
        st.pof;
        st.pob;
    }
    
    for(int i = 0; i < 4; i++){
        s.clear();
        lp = 0;
        for(int j = (st[i].F + 1) % n; j != st[(i + 1) % 4].F; j = (j + 1) % n){
            s += t[j];
        }
        move(mp(MAX, 0), i);
        while(lp < s.size()){
            block* b = solve();
            draw(b, i);
        }
        if(i < 3) move(mp(MAX, 0), i);
    }
    move(mp(ans.back().F, ans.front().S));

    vector<pii> pnt;
    pnt.eb(ans.back());
    for(int i = 0; i + 1 < ans.size(); i++){
        while(pnt.size() >= 2 && type(ans[i] - pnt.back()) == type(pnt.back() - pnt[(int)pnt.size() - 2])) pnt.pob;
        pnt.eb(ans[i]);
    }
    while(type(pnt.back() - pnt[(int)pnt.size() - 2]) == type(pnt.back() - pnt.front())) pnt.pob;
    for(pii i : pnt){
        cout << i.F << " " << i.S << "\n";
    }

    return 0;
}