首页 > 代码库 > 【poj3141】 Distant Galaxy
【poj3141】 Distant Galaxy
http://poj.org/problem?id=3141 (题目链接)
题意：给出平面上n个点，找出一个矩形，使边界上包含尽量多的点。
solution
不难发现，除非所有输入点都在同一行或同一列上，最优矩形的4条边上都至少有一个点。这样的话，我们可以枚举四条边穿过的点，然后统计点数。
考虑部分枚举，只枚举矩形上下界，用其它方法确定左右界。
设一条竖线i，用left[i]表示竖线左边位于上下界上单点数（不统计位于该竖线上的点），on[i]和on2[i]表示竖线上位于上下边界之间的点数（on[i]不统计位于上下界上的点，而on2[i]要统计）。这样，当左右边界分别为i，j时，矩形边界上的点数为left[j]-left[i]+on[i]+on2[j]。当右边界j确定时，on[i]-left[i]应最大。
枚举完上下边界后，我们花O(n)的时间按照从左到右的顺序for一遍所有的的点，计算left,on[i],on2[i]，然后枚举右边界j，同时维护on[i]-left[i]的最大值。
代码：
// poj3141#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi 3.1415926535898#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;struct point {int x,y;}a[10010];int y[10010],on[10010],on2[10010],L[10010],n;bool cmp(point a,point b) {return a.x<b.x;}int main() { int T=0; while (scanf("%d",&n)!=EOF && n) { T++; printf("Case %d: ",T); for (int i=0;i<n;i++) {scanf("%d%d",&a[i].x,&a[i].y);y[i]=a[i].y;} sort(a,a+n,cmp); sort(y,y+n); int m=unique(y,y+n)-y; if (m<=2) {printf("%d\n",n);continue;} int ans=0; for (int l=0;l<m;l++) for (int r=l+1;r<m;r++) { int ymin=y[l],ymax=y[r],k=0; memset(L,0,sizeof(L)); for (int i=0;i<n;i++) { if (i==0 || a[i].x!=a[i-1].x) { k++; on[k]=on2[k]=0; L[k]=L[k-1]+on2[k-1]-on[k-1]; } if (a[i].y>ymin && a[i].y<ymax) on[k]++; if (a[i].y>=ymin && a[i].y<=ymax) on2[k]++; } int M=0; for (int j=1;j<=k;j++) { ans=max(ans,L[j]+on2[j]+M); M=max(M,on[j]-L[j]); } } printf("%d\n",ans); } return 0;}
【poj3141】 Distant Galaxy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。