紫书习题8-19 UVa 1312 （枚举技巧）

这道题参考了https://www.cnblogs.com/20143605--pcx/p/4889518.html

这道题就是枚举矩形的宽，然后从宽再来枚举高。

具体是这样的，先把所有点的高度已经0和最高点储存起来，排个序。

然后就可以枚举所有可能的矩形的宽，然后可以理解为从左到右扫一遍，如果没有

点来阻碍的话，继续扫，如果有的话，那么矩形的长就是这次扫到阻碍时的横坐标与

上次扫到阻碍时的横坐标的差值，这一部分是刚好两端都有阻碍。

所以就可以枚举所有可能的矩形，然后算答案的时候按照正方形来算就ok了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

struct node

{

	int x, y;

}a[MAXN];

int d[MAXN];

bool cmp(node a, node b)

{

	if(a.x != b.x)

		return a.x < b.x;

	return a.y < b.y;

}

int main()

{

	int T, n, w, h;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d%d%d", &n, &w, &h);

		d[0] = 0; d[n+1] = h;

		REP(i, 1, n + 1)

		{

			scanf("%d%d", &a[i].x, &a[i].y);

			d[i] = a[i].y;

		}

		sort(a + 1, a + n + 1, cmp);

		sort(d, d + n + 2);

		int ans = 0, ansx, ansy;

		REP(i, 0, n + 1)

			REP(j, i + 1, n + 2)

			{

				int high = d[j], low = d[i], r = high - low, pre = 0, c;

				REP(k, 1, n + 1)

				{

					if(a[k].y <= low || a[k].y >= high) continue;

					c = a[k].x - pre;

					if(ans < min(r, c))

					{

						ans = min(r, c);

						ansx = pre;

						ansy = low;

					}

					pre = a[k].x;

				}

				c = w - pre;

				if(ans < min(r, c))

				{

					ans = min(r, c);

					ansx = pre;

					ansy = low;

				}

			}

		printf("%d %d %d\n", ansx, ansy, ans);

		if(T) puts("");

	}

	return 0;

}

巴特西

紫书习题8-19 UVa 1312 （枚举技巧）

最新文章

热门文章

巴特西

紫书 习题8-19 UVa 1312 （枚举技巧）

最新文章

热门文章

紫书习题8-19 UVa 1312 （枚举技巧）