Uva 1595 我真的越来越崇拜map容器了

一、题意

有kase组数据。
每组第一行一个n表示有n个点。
接下来n行输入这些点(x, y)。
要你判断每组点是否左右对称。

二、解析

先用vector存点，然后sort一下找到中心对称轴。
然后用map法来判断是否对称：具体而言，将对称轴左侧的点视为正标记，右侧的点视为负抵消，维护这样一个flag在map中，最后看是否所有点能恰好完全抵消，是的话说明对称，否则不对称。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define mp make_pair
using namespace std;
int kase, n;
vector<pair<int, int> > node;
map<pair<int, int>, int> flag;

int main() {
    cin >> kase;
    while(kase --) {
        node.clear(), flag.clear();
        cin >> n;
        while(n --) {
            int x, y;
            cin >> x >> y;
            node.push_back(mp(x, y));
        }
        sort(node.begin(), node.end());
        int d_mid;
        if(node.size() % 2) d_mid = node[node.size() / 2].first * 2;
        else d_mid = (node[node.size() / 2 - 1].first + node[node.size() / 2].first);
        for(auto p : node) {
            if(p.first * 2 < d_mid) flag[p] ++;
            else if(p.first * 2 > d_mid) {
                flag[mp(d_mid - p.first, p.second)] --;
            }
        }
        bool ok = 1;
        for(auto p : flag) if(p.second != 0) {
            ok = 0;
            break;
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
}

四、归纳

• 多组输入数据时记得clear全局容器
• 还是一样，做题前分析时间复杂度，不超时就大胆写。