You are given a stream of points on the X-Y plane. Design an algorithm that:
- Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.
- Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area.
- An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.
Implement the DetectSquares
class:
DetectSquares()
Initializes the object with an empty data structure.void add(int[] point)
Adds a new point point =[x, y]
to the data structure.int count(int[] point)
Counts the number of ways to form axis-aligned squares with point point =[x, y]
as described above.
Solution
每次查询时,给定一个点,我们要找出能构成正方形的数量。注意到,对于该点,那么另一个端点应该有相同的 \(x\) 或者有相同的 \(y\). 不妨固定 \(x\),找出 \(x\) 相同的所有 \(y\), 做差便得到可能的边长,然后检查另外两个点是否存在。
这里使用 \(map\) 套 \(map\) 来表示一个点被记录了多少次
点击查看代码
class DetectSquares {
private:
unordered_map<int, unordered_map<int,int>> dots;
public:
DetectSquares() {
}
void add(vector<int> point) {
int x = point[0], y = point[1];
dots[x][y]++;
}
int count(vector<int> point) {
int ans = 0;
int x1 = point[0], y1 = point[1];
if(dots.find(x1)==dots.end())return 0;
for(auto ele: dots[x1]){
int y2 = ele.first;
if(y2==y1)continue;
int dis = abs(y2-y1);
// case 1
int x2 = x1+dis;
if(dots.find(x2)!=dots.end() && dots[x2].find(y1)!=dots[x2].end() && dots[x2].find(y2)!=dots[x2].end()){
ans+= dots[x2][y1]*dots[x2][y2]*ele.second;
}
// case 2
x2 = x1-dis;
if(dots.find(x2)!=dots.end() && dots[x2].find(y1)!=dots[x2].end() && dots[x2].find(y2)!=dots[x2].end()){
ans+= dots[x2][y1]*dots[x2][y2]*ele.second;
}
}
return ans;
}
};
/**
* Your DetectSquares object will be instantiated and called as such:
* DetectSquares* obj = new DetectSquares();
* obj->add(point);
* int param_2 = obj->count(point);
*/