题目链接: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; }