博客

原题链接：

https://vjudge.net/problem/UVA-1312


分类：思维技巧

备注：巧妙枚举

因为树的数量很少，而且可以确定正方形的高度或者宽度以树的位置为边界，假设正方形的高度以树为边界，则枚举所有可能的高度坐标范围情况，在两个y坐标的范围内，又枚举宽度的情况即可，取小值为边长。

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int t,n,w,h,hav[maxn];
struct Point{
	int x,y;
	bool operator < (const Point& rhs) const{
		return x<rhs.x||(x==rhs.x&&y<rhs.y);
	}
}p[105];
int main(void){
	// freopen("in.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&w,&h);
		for(int i=0;i<n;i++){
			scanf("%d%d",&p[i].x,&p[i].y);
			hav[i]=p[i].y;
		}
		hav[n]=0,hav[n+1]=h;
		sort(p,p+n);
		sort(hav,hav+n+2);
		int sz=unique(hav,hav+n+2)-hav;
		int anslen=0,ansX,ansY;
		for(int i=0;i<sz;i++){
			for(int j=i+1;j<sz;j++){
				int befx=0,lenx,leny=hav[j]-hav[i];
				for(int k=0;k<n;k++){
					if(p[k].y<=hav[i]||p[k].y>=hav[j])continue;
					lenx=p[k].x-befx;
					int tmplen=min(lenx,leny);
					if(anslen<tmplen){
						anslen=tmplen;
						ansX=befx;
						ansY=hav[i];
					}
					befx=p[k].x;
				}
				lenx=w-befx;
				int tmplen=min(lenx,leny);
				if(anslen<tmplen){
					anslen=tmplen;
					ansX=befx;
					ansY=hav[i];
				}
			}
		}
		printf("%d %d %d\n",ansX,ansY,anslen);
		if(t)printf("\n");
	}
	return 0;
}