Codeforces 1184C1. Heidi and the Turing Test (Easy)题解

男娘i 2021-11-24 01:10 138阅读 0赞

原题链接：[C1. Heidi and the Turing Test (Easy)][C1. Heidi and the Turing Test _Easy]  
题意：给你一个平面直角坐标系，和其中一些点（共有\\(4 \\cdot n + 1\\)个）的坐标，你知道其中一定有一个正方形，并且这个正方形旁还有一个多余的点，现在请你把那个点找出来（注：每条边上的点不少于\\(n\\)个）  
题解：这一道题实实在在是一个坑，第一眼看到这个题的时候，第一反应就是找行和列上点的数量，大于等于\\(n\\)的就定为一条边，然而，种种特判让我防不胜防，无奈之下，放弃了这个想法。  
这一种方法不行，那暴力总可以吧，数据范围这么小，我们可以枚举删除的点，再暴力判断，就可以了。

#include <cstdio> #include <algorithm> using namespace std; #define Maxn 41 struct Node{ int x,y; friend bool operator <(Node p,Node q){ if(p.x==q.x){ return p.y<q.y; } return p.x<q.x; } }a[Maxn+5]; int mn(int a,int b){ return a<b?a:b; } int mx(int a,int b){ return a>b?a:b; } void swp(int &a,int &b){ int t=a; a=b; b=t; } int n,m; bool cmp(Node p,Node q){ if(p.y==q.y){ return p.x<q.x; } return p.y<q.y; } int x[Maxn+5],y[Maxn+5]; bool check(){ int mn_x=55,mn_y=55,mx_x=-1,mx_y=-1; for(int i=1;i<m;i++){ mn_x=mn(mn_x,x[i]); mn_y=mn(mn_y,y[i]); mx_x=mx(mx_x,x[i]); mx_y=mx(mx_y,y[i]); } if(mx_x-mn_x!=mx_y-mn_y){ return 0; } for(int i=1;i<m;i++){ if(x[i]!=mn_x&&x[i]!=mx_x&&y[i]!=mn_y&&y[i]!=mx_y){ return 0; } } return 1; } int main(){ scanf("%d",&n); m=(n<<2)+1; for(int i=1;i<=(n<<2)+1;i++){ scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+1+(n<<2)+1); for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ if(i==j){ continue; } if(j>i){ x[j-1]=a[j].x; y[j-1]=a[j].y; } else{ x[j]=a[j].x; y[j]=a[j].y; } } if(check()){ printf("%d %d\n",a[i].x,a[i].y); break; } } return 0; }

转载于:https://www.cnblogs.com/withhope/p/11147569.html

[C1. Heidi and the Turing Test _Easy]: https://codeforces.com/contest/1184/problem/C1