程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1382 Distant Galaxy (枚舉)

uva 1382 Distant Galaxy (枚舉)

編輯:C++入門知識

uva 1382 Distant Galaxy (枚舉)


uva 1382 Distant Galaxy


You are observing a distant galaxy using a telescope above the Astronomy Tower, and you think that a rectangle drawn in that galaxy whose edges are parallel to coordinate axes and contain maximum star systems on its edges has a great deal to do with the mysteries of universe. However you do not have the laptop with you, thus you have written the coordinates of all star systems down on a piece of paper and decide to work out the result later. Can you finish this task?

\epsfbox{p3694.eps}

Input

There are multiple test cases in the input file. Each test case starts with one integer N , (1$ \le$N$ \le$100) , the number of star systems on the telescope. N lines follow, each line consists of two integers: the X and Y coordinates of the K -th planet system. The absolute value of any coordinate is no more than 109 , and you can assume that the planets are arbitrarily distributed in the universe.

N = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, output the maximum value you have found on a single line in the format as indicated in the sample output.

Sample Input

10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
0

Sample Output

Case 1: 7



題目大意:給出n個點,問說一個平行與x軸和y軸的矩形,最多能有多少個點落在邊上。

解題思路:先枚舉上下邊界,然後從左到右掃,掃描一遍所有的點,計算L, on, on2數組,枚舉右邊界,維護on[i] - L[i]的最大值。


#include
#include
#include
#include
using namespace std;
int n, y[1005], on[1005], on2[1005], L[1005];  
struct point {
	int x, y;
};  
int cmp(point a, point b) {
	return a.x < b.x;
}
point p[1005];
int getAns(){  
	int ans = 0;  
	sort(p, p + n, cmp);  
	sort(y, y + n);  
	int m = unique(y, y + n) - y;  //統計具有不同y坐標的點的個數
	if(m <= 2) return n;  
	for(int a = 0; a < m; a++)          
		for(int b = a + 1; b < m; b++){  
			int miny = y[a], maxy = y[b], k = 0;  //枚舉上下邊
			memset(on, 0, sizeof(on));  
			memset(on2, 0, sizeof(on2));  
			memset(L, 0, sizeof(L));  
			for(int i = 0; i < n; i++){         
				if(!i || p[i].x != p[i-1].x){  
					k++;  
					if(k > 1) L[k] = L[k - 1] + on2[k - 1] - on[k - 1]; //on2記錄邊界,on沒記錄邊界,on2-on就是邊界上的點的個數, 加上上一條豎線左側,就是當前豎線左側點的個數 
				}  
				if(p[i].y < maxy && p[i].y > miny) on[k]++;  
				if(p[i].y <= maxy && p[i].y >= miny) on2[k]++;  
			}  
			if(k <= 2) return n;  
			int Max = 0;  
			for(int i = 1; i <= k; i++){   
				ans = max(ans, L[i] + on2[i] + Max);  //維護Max
				Max = max(Max, on[i] - L[i]);  
			}  
		}  
	return ans;  
}  
int main(){  
	int Case = 1;  
	while(scanf("%d", &n), 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", Case++, getAns());  
	}  
	return 0;  
}




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved