---
# System prepended metadata

title: UVA 476 ★
tags: [CPE 一顆星]

---

## 題目
[點我](https://onlinejudge.org/external/4/476.pdf)

## 題意
先給一堆長方形，再給一堆點，問每個點在哪個長方形內
- 點可能不在長方形內
- 點可能在很多長方形內


## 演算法

## 程式碼
```cpp=
#include <bits/stdc++.h>

using namespace std;

int inWhichFigure(vector <vector <double>> figure , pair <double , double> point){
    for(int i = 0 ; i < figure.size() ; i++){
        if(figure[i][0] < point.first && point.first < figure[i][2]){ //x
            if(figure[i][3] < point.second && point.second < figure[i][1]){ //y
                return i + 1;
            }
        }
    }
    return 0;
}

int main(){
    char cha;
    vector <vector <double>> figure;
    while(1){
        cin >> cha;
        if(cha != 'r') break;
        vector <double> coordinate(4);
        for(int i = 0 ; i < 4 ; i++){
            cin >> coordinate[i];
        }
        figure.push_back(coordinate);
    }
    
    double x , y;
    int pointIdx = 1;
    while(1){
        cin >> x >> y;
        if(x == 9999.9 && y == 9999.9) break;
        int whichFigure = inWhichFigure(figure , make_pair(x , y));
        if(whichFigure == 0){
            printf("Point %d is not contained in any figure\n" , pointIdx);   
        }
        else{
            printf("Point %d is contained in figure %d\n" , pointIdx , whichFigure);
        }
        pointIdx++;
    }
    
}

```

## 我犯的錯
沒有規定好i從0還是1開始，被自己搞混
沒注意重疊的問題
提交兩次才AC

