题解：CF1184C1 Heidi and the Turing Test (Easy)

思路

我们首先需要求出

4

条边。但是如果用普通的算法来算了话，如果特殊的点在正方形外，就会错误。

于是乎我们观察题面，可以得知每条边至少有

n

个点（英文原版有，洛谷翻译没有）。

其实我们也用不到这个特殊性质，因为正方形有

4

个顶点，这样每条边上就至少有

2

个点，而特殊点的边上（如果不与其它边重叠，重叠了话我们可以省略，已经找到边了）只有

1

个点。

所以我们可以用一个桶来记录边上有多少个点，然后枚举边，如果边上点数大于

1

了话，那这条边就是正方形的一条边。

最后再枚举每个点是否在边上。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x[45],y[45],minx=INT_MAX,maxx=INT_MIN,miny=INT_MAX,maxy=INT_MIN,i,j,hx[55],hy[55];
signed main()
{
	cin>>n;
	for(i=1;i<=4*n+1;i++)
	{
		cin>>x[i]>>y[i];
		hx[x[i]]++;
		hy[y[i]]++;
	}
	for(i=0;i<=50;i++)
	{
		if(hx[i]>1)
		{
			minx=min(minx,i);
			maxx=max(maxx,i);
		}
	}
	for(i=0;i<=50;i++)
	{
		if(hy[i]>1)
		{
			miny=min(miny,i);
			maxy=max(maxy,i);
		}
	}
	for(i=1;i<=4*n+1;i++)
	{
		if((x[i]<minx||x[i]>maxx)||(y[i]<miny||y[i]>maxy||(y[i]>miny&&y[i]<maxy&&(x[i]>minx&&x[i]<maxx))))
		{
			cout<<x[i]<<" "<<y[i];
			break;
		}
	}
	return 0;
}

题解：CF1184C1 Heidi and the Turing Test (Easy)

文章操作

思路

代码

相关推荐

评论

题解：CF1184C1 Heidi and the Turing Test (Easy)