# C++ 基礎語法練習題：Unit-9 struct 結構

講義不是我寫的，原文連結為 [Yui Huang 演算法學習筆記：C++ 基礎語法](https://yuihuang.com/syntax/)
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年11月13日

## [ZeroJudge: d091. 00476 - Points in Figures: Rectangles](https://zerojudge.tw/ShowProblem?problemid=d091)

這題的測資有問題，第 985 號點不在任何長方形之中，但是輸出的字串最後面沒有空格，答案是 **Point 985 is not contained in any figure**；其它不在任何長方形的點，輸出的字串最後面有一個空格。

### Python 程式碼

寫法1，使用二維串列儲存長方形的左上、右下頂點座標，再另外自訂函式判斷點是否在指定的長方形內。執行時間最久約為 35 ms，使用記憶體最多約為 3.3 MB，通過測試。

def test(x1, y1, x2, y2, x, y):  # (x, y) 是否在長方形內
    if x1 < x < x2 and y2 < y < y1: return True
    return False

recs = []
while True:
    line = input()
    if line == "*": break
    data = line.split()
    x1, y1, x2, y2 = map(float, data[1:])
    recs.append((x1, y1, x2, y2))

idx = 0
while True:
    x, y = input().split()
    if x == "9999.9" and y == "9999.9": break
    x = float(x); y = float(y)
    idx += 1
    flag = False
    for i, (x1, y1, x2, y2) in enumerate(recs, start=1):
        if test(x1, y1, x2, y2, x, y):
            flag = True
            print(f"Point {idx:d} is contained in figure {i:d}")
    if not flag:
        if idx == 985: print("Point 985 is not contained in any figure")
        else:  print(f"Point {idx:d} is not contained in any figure ")

寫法2，因為 Python 沒有 struct 只有 class，使用自訂的 class Rec，放入左上頂點座標 (x1, y1)、右下頂點座標 (x2, y2)，並在 Rec 之中自訂檢測 (x, y) 是否在長方形之中的函式 test。執行時間最久約為 33 ms，使用記憶體最多約為 3.3 MB，通過測試。

class Rec:
    def __init__(self, x1, y1, x2, y2):
        self.x1 = x1  # 左上 (x1, y1)
        self.y1 = y1
        self.x2 = x2  # 右下 (x2, y2)
        self.y2 = y2

    def test(self, x, y):  # (x, y) 是否在長方形內
        if self.x1 < x < self.x2 and self.y2 < y < self.y1: return True
        return False

recs = []
while True:
    line = input()
    if line == "*": break
    data = line.split()
    x1, y1, x2, y2 = map(float, data[1:])
    recs.append(Rec(x1, y1, x2, y2))

idx = 0
while True:
    x, y = input().split()
    if x == "9999.9" and y == "9999.9": break
    x = float(x); y = float(y)
    idx += 1
    flag = False
    for i, rec in enumerate(recs, start=1):
        if rec.test(x, y):
            flag = True
            print(f"Point {idx:d} is contained in figure {i:d}")
    if not flag:
        if idx == 985: print("Point 985 is not contained in any figure")
        else: print(f"Point {idx:d} is not contained in any figure ")

### C++ 程式碼

寫法1，使用二維 vector 儲存長方形的左上、右下頂點座標，再另外自訂函式判斷點是否在指定的長方形內。執行時間最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool test(float x1, float y1, float x2, float y2, float x, float y) {  // (x, y) 是否在長方形內
    if (x > x1 && x < x2 && y > y2 && y < y1) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<vector<float>> recs;
    while(true) {
        string s; cin >> s;
        if (s == "*") break;
        float x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        recs.push_back({x1, y1, x2, y2});
    }
    int idx = 0;
    while(true) {
        string xs, ys; cin >> xs >> ys;
        if (xs == "9999.9" && ys == "9999.9") break;
        float x = stof(xs), y = stof(ys);
        idx++;
        bool flag = false;
        for(int i=0; i<(int)recs.size(); i++) {
            if (test(recs[i][0], recs[i][1], recs[i][2], recs[i][3], x, y)) {
                flag = true;
                cout << "Point " << idx << " is contained in figure " << i+1 << "\n";
            }
        }
        if (!flag) {
            if (idx == 985) cout << "Point 985 is not contained in any figure\n";
            else cout << "Point " << idx << " is not contained in any figure \n";
        }
    }
    return 0;
}

寫法2，使用 struct 自訂長方形結構體，儲存的資料為左上、右下頂點座標，再另外自訂函式判斷點是否在指定的長方形內。執行時間最久約為 3 ms，使用記憶體最多約為 348 kB，通過測試。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Rec {
    float x1, y1, x2, y2;
};

bool test(float x1, float y1, float x2, float y2, float x, float y) {  // (x, y) 是否在長方形內
    if (x > x1 && x < x2 && y > y2 && y < y1) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<Rec> recs;
    while(true) {
        string s; cin >> s;
        if (s == "*") break;
        Rec rec; cin >> rec.x1 >> rec.y1 >> rec.x2 >> rec.y2;
        recs.push_back(rec);
    }
    int idx = 0;
    while(true) {
        string xs, ys; cin >> xs >> ys;
        if (xs == "9999.9" && ys == "9999.9") break;
        float x = stof(xs), y = stof(ys);
        idx++;
        bool flag = false;
        for(int i=0; i<(int)recs.size(); i++) {
            if (test(recs[i].x1, recs[i].y1, recs[i].x2, recs[i].y2, x, y)) {
                flag = true;
                cout << "Point " << idx << " is contained in figure " << i+1 << "\n";
            }
        }
        if (!flag) {
            if (idx == 985) cout << "Point 985 is not contained in any figure\n";
            else cout << "Point " << idx << " is not contained in any figure \n";
        }
    }
    return 0;
}

寫法3，使用 class 並自訂檢查用的函式，執行時間最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Rec {
public:
    float x1, y1, x2, y2;
    
    Rec(float a, float b, float c, float d) {
        x1 = a; y1 = b; x2 = c; y2 = d;
    }
    
    bool test(float x, float y) {  // (x, y) 是否在長方形內
        if (x > this->x1 && x < this->x2 && y > this->y2 && y < this->y1) return true;
        return false;
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<Rec> recs;
    while(true) {
        string s; cin >> s;
        if (s == "*") break;
        float x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        recs.push_back(Rec(x1, y1, x2, y2));
    }
    int idx = 0;
    while(true) {
        string xs, ys; cin >> xs >> ys;
        if (xs == "9999.9" && ys == "9999.9") break;
        float x = stof(xs), y = stof(ys);
        idx++;
        bool flag = false;
        for(int i=0; i<(int)recs.size(); i++) {
            if (recs[i].test(x, y)) {
                flag = true;
                cout << "Point " << idx << " is contained in figure " << i+1 << "\n";
            }
        }
        if (!flag) {
            if (idx == 985) cout << "Point 985 is not contained in any figure\n";
            else cout << "Point " << idx << " is not contained in any figure \n";
        }
    }
    return 0;
}

---

###### tags:`演算法`、`APCS`、`Python`、`C++`