本文主要是介绍UVA - 1382 Distant Galaxy，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出平面上的n个点，找到一个矩形，使得边界上包含尽量多的点
思路：如果单纯的枚举四条边再计数的话显然时间是不够的，，所以我们可以只枚举上下边界，用on[i],on2[i]表示竖线上位于上下边界之间的点数（区别在on[i]不统计位于上下边界上的点），这样，给定左右边界i,j的时候，矩形边界上的点数为left[j]-left[i]+on[i]+on2[j]，当右边界确定的时候，on[i]-left[i]应最大，不断的去维护它的最大值就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;struct point{int x,y;bool operator < (const point &s)const {return x < s.x;}
}P[MAXN];
int n,m,y[MAXN],on[MAXN],on2[MAXN],Left[MAXN];int solve(){sort(P,P+n);sort(y,y+n);m = unique(y,y+n) - y;if (m <= 2)return n;int ans = 0;for (int a = 0; a < m; a++)for (int b = a+1; b < m; b++){int ymin = y[a],ymax = y[b];int k = 0;for (int i = 0; i < n; i++){if (i == 0 || P[i].x != P[i-1].x){k++;on[k] = on2[k] = 0;Left[k] = Left[k-1] + on2[k-1] - on[k-1];}if (P[i].y > ymin && P[i].y < ymax)on[k]++;if (P[i].y >= ymin && P[i].y <= ymax)on2[k]++;}if (k < 2)return n;int M = 0;for (int j = 1; j <= k; j++){ans = max(ans,Left[j]+on2[j]+M);M = max(M,on[j]-Left[j]);}}return ans;
}int main(){int cas = 0;while (scanf("%d",&n) != EOF && n){for (int i = 0; i < n; i++){scanf("%d%d",&P[i].x,&P[i].y);y[i] = P[i].y;}printf("Case %d: %d\n",++cas,solve());}return 0;
}这篇关于UVA - 1382 Distant Galaxy的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
