题意:给出平面上的n个点,找一个矩形,使得边界上包含尽量多的点。
代码:
View Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #define DEBUG 5 using namespace std; 6 struct ZZ{ 7 int x, y; 8 bool operator < (const ZZ& p) const{ 9 return x<p.x; 10 } 11 }; 12 int max(int a, int b){ 13 return a>b?a:b; 14 } 15 const int MAXN = 100 + 10; 16 ZZ p[MAXN]; 17 int n, m, y[MAXN], on[MAXN], on2[MAXN], zl[MAXN]; 18 19 int solve(){ 20 sort(p, p+n); 21 sort(y, y+n); 22 m = unique(y, y+n) - y; 23 if(m<=2) return n; 24 25 int ans = 0; 26 for(int a=0; a<m; a++){ 27 for(int b=a+1; b<m; b++){ 28 int ymin = y[a]; 29 int ymax = y[b]; 30 31 int k = 0; 32 for(int i=0; i<n; i++){ 33 if(i==0 || p[i].x!=p[i-1].x){ 34 k++; 35 on[k] = on2[k] = 0; 36 if(k==0) zl[k] = 0; 37 else zl[k] = zl[k-1] + on2[k-1] - on[k-1]; 38 } 39 if(p[i].y>ymin && p[i].y<ymax) on[k]++; 40 if(p[i].y>=ymin && p[i].y<=ymax) on2[k]++; 41 } 42 if(k<=2) return n; 43 44 int M = 0; 45 for(int j=1; j<=k; j++){ 46 ans = max(ans, zl[j]+on2[j]+M); 47 M = max(M, on[j]-zl[j]); 48 } 49 } 50 } 51 return ans; 52 } 53 int main(){ 54 #ifndef DEBUG 55 freopen("in.txt", "r", stdin); 56 #endif 57 int cas=0; 58 while(scanf("%d", &n)==1 && n){ 59 for(int i=0; i<n; i++){ 60 scanf("%d%d", &p[i].x, &p[i].y); 61 y[i]=p[i].y; 62 } 63 printf("Case %d: %d\n", ++cas, solve()); 64 } 65 return 0; 66 }
这题感觉自己还是没理解透彻。