HDU3299 – Distant Galaxy(枚举+扫描)

题目链接：HDU3299

【题意】给出N(<=100)个点的坐标，每个坐标的绝对值<=10^9，求一个矩形使得该矩形的边上有最多的点。

【分析】求的是矩形的边上有最多的点，最容易想到枚举4条边，然后扫描N个点求当前4条边上的单数，最后取最大，但是这样做的复杂度是n^5的，显然不能接受。需要优化。

可以只枚举矩形的上下两条边，需要快速求出左右两条变上有几个点，把x坐标和y坐标都离散，接下去就可以枚举矩形上下两边的y坐标，然后sum[i]表示每个x竖线以及它左边的在上下边上的点数，就是前缀和。然后还要用on[i]记录在竖线i同时在上下边之间的点数(不包含上下边上的点)，这样以竖线i为左面的边，竖线j为右面的边的话可以得到当前矩形四条边上的点数=sum[j]-sum[i-1]+on[i]+on[j];如果j确定，只要从左往右扫描竖线维护on[i]-sum[i-1]为最大，最终维护答案就可以得到最终答案，具体看代码。

【AC CODE】46ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100+10;
struct NODE{
	int x, y;
}p[MAXN];
set<int> visx, visy;
int x[MAXN],y[MAXN], cntx, cnty, sum[MAXN], on[MAXN];
//sum[i]记录竖线i以及左边的上下边包含的点数,on[i]表示竖线i(不算上下边)上的点数
//左右边a,b之间(即由两竖线a,b和上下边i,j组成的矩形)上的总点数为sum[j]-sum[i-1]+on[i]+on[j]
int num[MAXN];

int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int n, count = 0;
	while(~scanf("%d%*c", &n) && n)
	{
		visx.clear();
		visy.clear();
		cntx = cnty = 0;
		rep(i,0,n)
		{
			scanf("%d %d%*c",&p[i].x, &p[i].y);
			if(visx.find(p[i].x) == visx.end())
			{
				visx.insert(p[i].x);
				x[cntx++] = p[i].x;
			}
			if(visy.find(p[i].y) == visy.end())
			{
				visy.insert(p[i].y);
				y[cnty++] = p[i].y;
			}
		}
		if(cnty == 1)
		{
			printf("Case %d: %d\n", ++count,n);
			continue;
		}
		sort(y,y+cnty);
		sort(x,x+cntx);
		int ans = 0;
		rep(i,0,cnty)//枚举下边
		{
			rep(j,i+1,cnty)//枚举上边
			{
				clc(num,0);
				clc(on,0);
				rep(k,0,n)//计算num[]
				{
					if(p[k].y == y[i] || p[k].y == y[j])
						num[lower_bound(x,x+cntx,p[k].x)-x+1]++;
					else if(p[k].y > y[i] && p[k].y < y[j])
						on[lower_bound(x,x+cntx,p[k].x)-x+1]++;
				}
				int mx = 0;//mx维护on[k]-sum[k-1]
				repe(k,1,cntx)
				{
					sum[k] = sum[k-1]+num[k];
					ans = max(sum[k]+mx+on[k], ans);
					mx = max(mx, on[k]-sum[k-1]);
				}
			}
		}
		printf("Case %d: %d\n", ++count,ans);
	}
	return 0;
}