# 2025 University/College IC Design Contest Cell-Based IC Design Category for Graduate Level

## 題目就是要動態維護凸包
依據題目轉成C++的形式可以這樣寫，編譯完之後就用stdio吃pattern就可以了
`a.out < pattern1.dat`

#include <bits/stdc++.h>
using namespace std;

void run(vector<array<int, 2>> &points)
{

    vector<int> nxt_idx(points.size(), -1);
    nxt_idx[1] = 2;
    nxt_idx[0] = 1;
    nxt_idx[2] = 0;
    int dx0 = points[1][0] - points[0][0], dx1 = points[2][0] - points[1][0],
        dy0 = points[1][1] - points[0][1], dy1 = points[2][1] - points[1][1];
    bool circle_sign = (dx0 * dy1 - dx1 * dy0) < 0;
    int start_idx = 0, prev_idx = 0, cur_idx = 0, next_idx = 0;
    for (int i = 3; i < points.size(); i++)
    {
        cur_idx = start_idx;
        next_idx = nxt_idx[cur_idx];
        dx0 = points[next_idx][0] - points[cur_idx][0];
        dy0 = points[next_idx][1] - points[cur_idx][1];
        dx1 = points[i][0] - points[cur_idx][0];
        dy1 = points[i][1] - points[cur_idx][1];
        int cp = dx0 * dy1 - dx1 * dy0;
        bool circle_sign_cur = cp < 0;
        bool prev_difside = 0, prev_zero = 0;
        bool cur_difside = circle_sign_cur != circle_sign, cur_zero = cp == 0;
        if (cur_zero)
            cur_difside = 0;
        // cout << "first difside " << cur_difside << " first sign " << cur_zero << endl;
        for (;;)
        {
            prev_idx = cur_idx;
            cur_idx = next_idx;
            next_idx = nxt_idx[next_idx];
            prev_difside = cur_difside;
            prev_zero = cur_zero;
            dx0 = points[next_idx][0] - points[cur_idx][0];
            dy0 = points[next_idx][1] - points[cur_idx][1];
            dx1 = points[i][0] - points[cur_idx][0];
            dy1 = points[i][1] - points[cur_idx][1];
            cp = dx0 * dy1 - dx1 * dy0;
            circle_sign_cur = cp < 0;
            cur_zero = cp == 0;
            cur_difside = circle_sign_cur != circle_sign;
            // cout << "i = " << i << " cur pos " << cur_idx << " " << points[cur_idx][0] << " " << points[cur_idx][1] << endl;

            if (cur_zero)
                cur_difside = 0;
            if ((prev_difside || prev_zero) && (cur_difside || (cur_zero && !prev_zero)))
            {
                cout << "pop  " << cur_idx + 1 << "  : " << points[cur_idx][0] << " " << points[cur_idx][1] << endl;
            }

            if (cur_difside)
            {

                if (prev_zero)
                    nxt_idx[prev_idx] = i;
                else
                    nxt_idx[cur_idx] = i;
            }
            else if (prev_difside)
            {
                if (cur_zero)
                    nxt_idx[i] = next_idx;
                else
                    nxt_idx[i] = cur_idx;
            }

            // cout << "cur_idx " << cur_idx << " next_idx " << next_idx << endl;
            if (cur_idx == start_idx)
                break;
        }
        if (nxt_idx[i] == -1)
            cout << "pop  " << i + 1 << "  : " << points[i][0] << " " << points[i][1] << endl;
        else
            start_idx = i;
    }
    cout << "convex : " << start_idx + 1 << " ";
    for (int nxp = nxt_idx[start_idx]; nxp != start_idx; nxp = nxt_idx[nxp])
    {
        cout << nxp + 1 << " ";
    }
    cout << endl;
}

int main()
{
    int x, y, cnt = 0;
    string type;
    vector<array<int, 2>> points, rmlist;
    while (cin >> type)
    {
        cin >> x >> y;
        if (type[0] == 'A')
        {
            cnt++;
            points.push_back({x, y});
        }
        else if (type[0] == 'R')
        {
            rmlist.push_back({x, y});
        }
    }
    run(points);
    return 0;
}

邏輯上是針對每次新增的點對現有凸包繞一圈檢查是否在凸包內側，可以用外積向量的方向(正負值)判斷，另外要注意的是外積為0時的特殊判斷，上面的cur_idx是當前邊的出發點，next_idx是當前邊的結束點，要外積的另一個向量的出發點也是cur_idx，結束點是要檢查的新增點。凸包的連接關係由nxt_idx維護，如果要拋棄點的話只要改變nxt_idx就能將該點斷開。

從上面的code可以觀察有很多計算步驟非常相似，可以寫成共用的模組，像是外積向量的準備與外積本身，剩下要做的就是更新nxt_idx和state machine狀態轉移。細節處理完就大功告成了，裡面能優化delay的部分就是外積的乘法操作，想要做的更好可能要在這邊下功夫。之後有時間再試試看能不能pipeline繞一整圈的過程，減少需要的時間。

太久沒寫RTL以及為了HDL仔細優化c++ code，這題寫起來還蠻卡的，現在越來越覺得寫verilog前一定要先將對應的software model寫出來。雖然這樣寫的RTL很像是翻譯，但是優化電路和設計state machine時會比較有感覺，寫RTL和之後驗證才有個依據，

之後再補充RTL。

### To be continued.