week4-[二維數組]平面上的點

題目描述

有 $N$ 個二維平面上的點，每個點的坐標都是整數且坐標范圍都在 $0～999$ 之間，求其中出現最頻繁的點的出現次數及其坐標。

輸入格式

第一行有一個整數 $N$，表示平面上點的個數。

接下來 $N$ 行，每行有兩個整數，表示一個平面上的點的 $x,y$ 二維坐標。

輸出格式

輸出的第一行為一個整數，表示平面中的點出現的最多次數。

接下來輸出每行兩個整數，表示出現最頻繁的點的二維坐標。

• 如果有多個點均為最頻繁出現的點，則輸出包括多行。輸出的順序為：先按照 $x$ 坐標從小到大輸出，再按照 $y$ 坐標從小到大輸出。

樣例 #1

樣例輸入 #1

5
1 2
3 2
2 8
1 2
6 10

樣例輸出 #1

2
1 2

樣例 #2

樣例輸入 #2

7
1 5
0 3
8 2
4 2
1 5
6 7
0 3

樣例輸出 #2

2
0 3
1 5

樣例 #3

樣例輸入 #3

10
5 3
5 3
5 2
2 6
5 3
2 6
5 2
2 6
1 8
5 2

樣例輸出 #3

3
2 6
5 2
5 3

提示

數據范圍

對于所有數據，$1\le n\le 50000$。

這題考察的是 二維點的統計與排序，重點在于：

1. 統計每個點出現次數
2. 找到最大出現次數
3. 輸出所有達到最大次數的點，按坐標排序

---

🔎 解題思路

1. 存儲與統計
   • 點的坐標范圍在 [0,999]，但 n 可達 50000，直接開 1000×1000 數組也行（內存約 1MB），也可以用 map<pair<int,int>, int> 來統計次數。
   • 推薦用 map 或 unordered_map，因為題目數據范圍比較大，但點可能很稀疏。
2. 尋找最大值
   • 遍歷統計結果，找到出現次數的最大值 maxCnt。
3. 收集答案并排序
   • 遍歷統計表，找出所有次數等于 maxCnt 的點，放到數組里。
   • 對結果按照 (x,y) 排序：先比 x，若相等再比 y。

---

📝 C++ 實現

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin >> n;map<pair<int,int>, int> freq;for (int i = 0; i < n; i++) {int x, y;cin >> x >> y;freq[{x, y}]++;}int maxCnt = 0;for (auto &p : freq) {if (p.second > maxCnt) maxCnt = p.second;}vector<pair<int,int>> ans;for (auto &p : freq) {if (p.second == maxCnt) ans.push_back(p.first);}sort(ans.begin(), ans.end()); // pair 默認先按 first 再按 second 排序cout << maxCnt << "\n";for (auto &pt : ans) {cout << pt.first << " " << pt.second << "\n";}return 0;
}