CF1184C1题解

66xyyd · 2023-08-10 16:13:03 · 题解

题意

给定 4n+1 个点的位置，其中 4n 个点均在某一边与坐标轴平行的正方形的边界上，求剩下的 1 个点的坐标。（其实翻译说的挺清楚的）

题解

在了解完题意后，我们先来看看我们的判断依据。

如果有一个正方形，四条边都与坐标轴平行，那么正方形的左下点的 x 坐标是所有边上点中 x 坐标最小的那个，y 坐标是所有边上点中 y 坐标最小的那个；右上点的 x 坐标是所有边上点中 x 坐标最大的那个，y 坐标是所有边上点中 y 坐标最大的那个。记左下点为 min_x,min_y，右上点为 max_x,max_y。

（图片挂了）

同时我们还发现，正方形的左下点 (min_x,min_y) 与右上点 (max_x,max_y) 的 x 坐标之差和 y 坐标之差相等，都是正方形的边长；所有正方形上的点 x,y 中 x 坐标要么是 min_x，要么是 max_x，y 坐标要么是 min_y，要么是 max_y。

看到这，判断一个点集是否为某一正方形的边界（以下默认正方形的各个边平行于坐标轴）的方法其实已经出现了。首先统计点集中的四个极值 max_x,max_y,min_x,min_y。我们知道正方形的边长是固定的，max_x-min_x 与 max_y-min_y 相等。如果不是，该点集就不是任何正方形的边界。否则我们比较点集中所有点，如果有一点 x 坐标或 y 坐标不为极值，也不是任何正方形的边界。

接下来我们只用枚举是哪个点 i 不属于正方形的边界，在循环到这个点时跳过即可。如果去掉 i 之后剩下的所有点都属于正方形的边界，那么 i 就是我们要找的，直接输出坐标即可。

#include<iostream>
using namespace std;
pair<int,int> a[101];//first表示x坐标，second表示y坐标
int n;
int main(){
    cin >> n;
    n=n*4+1;//实际有4n+1点，别被坑了
    for(int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
    }
    for(int i=1;i<=n;i++){
        bool flag=true;//用来记录当前点集是否可构成正方形边界
        int maxx=-1,maxy=-1,minx=2147483647,miny=2147483647;
        for(int j=1;j<=n;j++){//计算四个极值（x,y极大&极小）
            if(i==j){
                continue;
            }
            maxx=max(maxx,a[j].first);
            maxy=max(maxy,a[j].second);
            minx=min(minx,a[j].first);
            miny=min(miny,a[j].second);
        }
        if(maxx-minx!=maxy-miny)    continue;//说明该点集不是任何正方形的边界，跳过此i即可
        for(int j=1;j<=n;j++){
            if(i==j)    continue;
            if(!(a[j].first==maxx || a[j].second==maxy || a[j].first==minx || a[j].second==miny)){//j不是极值，记录
                flag=false;
            }
        }
        if(flag){//可构成，i不属于正方形的边
            cout << a[i].first << ' ' << a[i].second;
            return 0;
        }
    }
    cout << "Silly CF";//这句被输出意味着数据有问题
    return 0;
}