题目

现在有一组给定点的坐标，求出坐标系中在上下左右方向上都有给定点的点的数量。注意：目标点不能和给定点重合，另外要求的是“上下左右方向上”而不是简单的“上下左右”；

题解

解析

根据题目的描述，需要找到坐标系中所有满足以下条件的点（称为目标点）：

1. 目标点不能与给定的点重合；
2. 在目标点的上、下、左、右方向上，都至少存在一个给定的点；
3. 这里的上、下、左、右方向，指的是同一列（x坐标相同）或同一行（y坐标相同），而不是简单的相邻；

设计

算法说明：

1. 读取所有给定的点，并将它们存储在一个向量和一个集合中。集合用于快速检查某个点是否是给定的点；
2. 预处理：为每个唯一的x坐标创建一个排序的y坐标列表，为每个唯一的y坐标创建一个排序的x坐标列表。这有助于后续步骤中快速找到某个方向上是否存在给定的点；
3. 遍历所有可能的x和y坐标的组合，跳过那些已经是给定点的坐标；
4. 对于每个候选点，使用二分查找在对应的排序列表中检查在上、下、左、右四个方向上是否存在给定的点；
5. 如果某个候选点在四个方向上都有给定的点，计数器加一。

代码

int main()
{
    int N;
    cin >> N;
    vector<Point> points(N);
    set<pair<int, int>> pointSet; // 用于快速查找点是否存在

    // 读取给定的点
    for (int i = 0; i < N; ++i)
    {
        cin >> points[i].x >> points[i].y;
        pointSet.insert({points[i].x, points[i].y});
    }

    // 获取所有唯一的x和y坐标
    set<int> xSet, ySet;
    for (const auto &p: points)
    {
        xSet.insert(p.x);
        ySet.insert(p.y);
    }

    // 对于每个x，获取对应的所有y坐标并排序
    map<int, vector<int>> xToYs;
    for (const auto &p: points)
    {
        xToYs[p.x].push_back(p.y);
    }
    for (auto &entry: xToYs)
    {
        sort(entry.second.begin(), entry.second.end());
    }

    // 对于每个y，获取对应的所有x坐标并排序
    map<int, vector<int>> yToXs;
    for (const auto &p: points)
    {
        yToXs[p.y].push_back(p.x);
    }
    for (auto &entry: yToXs)
    {
        sort(entry.second.begin(), entry.second.end());
    }

    int count = 0;

    // 枚举所有可能的候选点
    for (int x: xSet)
    {
        for (int y: ySet)
        {
            // 跳过给定的点
            if (pointSet.count({x, y}))
            {
                continue;
            }

            // 检查上方向是否有点
            auto &ys = xToYs[x];
            auto it = upper_bound(ys.begin(), ys.end(), y);
            bool hasUp = it != ys.end();

            // 检查下方向是否有点
            bool hasDown = it != ys.begin() && ys.size() > 0 && *(prev(it)) < y;

            // 检查右方向是否有点
            auto &xs = yToXs[y];
            auto it2 = upper_bound(xs.begin(), xs.end(), x);
            bool hasRight = it2 != xs.end();

            // 检查左方向是否有点
            bool hasLeft = it2 != xs.begin() && xs.size() > 0 && *(prev(it2)) < x;

            // 如果四个方向都有点，计数加一
            if (hasUp && hasDown && hasLeft && hasRight)
            {
                count++;
            }
        }
    }

    cout << count << endl;
    return 0;
}