程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 1382 - Distant Galaxy（技巧枚舉+離散化）

1382 - Distant Galaxy（技巧枚舉+離散化）

編輯：C++入門知識

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 10⁹ , 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

Sample Output

Case 1: 7

題意：給定一些坐標的點，然後求出一個矩形上面點數最多

思路：由於坐標很大並且有負數，所以利用map離散化，然後每次枚舉上邊界和下邊界，然後從左邊界一直往右邊界推，類似前綴求和思想維護一個最小值即可。原來沒特判點全在一條直線的情況一直WA。。坑啊

代碼：

#include 
#include 
#include 
#include 
#include 
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

#define INF 0x3f3f3f3f
using namespace std;

const int N = 105;

int n, x[N], y[N], xn, yn, g[N][N], flag1, flag2;

vector xp[N], yp[N];
map xv, yv;

struct Point {
	int x, y;
} p[N];

bool cmp(Point a, Point b) {
	return a.y < b.y;
}

void init() {
	flag1 = flag2 = 0; int j;
	xn = 1; yn = 1;
	memset(g, 0, sizeof(g));
	memset(xp, 0, sizeof(xp));
	memset(yp, 0, sizeof(yp));
	xv.clear(); yv.clear();
	for (j = 0; j < n; j++) {
		scanf("%d%d", &p[j].x, &p[j].y);
	}
	for (j = 1; j < n; j++) {
		if (p[j].x != p[j - 1].x)
			flag1 = 1;
		if (p[j].y != p[j - 1].y)
			flag2 = 1;
	}
	sort(p, p + n, cmp);
	for (int i = 0; i < n; i++) {
		int xx = p[i].x, yy = p[i].y;
		if (!xv[xx]) {
			xv[xx] = xn;
			x[xn++] = xx;
		}
		if (!yv[yy]) {
			yv[yy] = yn;
			y[yn++] = yy;
		}
		g[xv[xx]][yv[yy]] = 1;
		xp[xv[xx]].push_back(yy);
		yp[yv[yy]].push_back(xx);
	}
}

int solve() {
	if (flag1 == 0 || flag2 == 0)
		return n;
	int ans = 0;
	for (int i = 1; i < xn; i++) {
		for (int j = i + 1; j < xn; j++) {
			int Min = INF;
			for (int k = 1; k < yn; k++) {
				int s = 0, h = 0;
				for (int x1 = 0; x1 < xp[i].size(); x1++) {
					if (xp[i][x1] < y[k]) h++;
				}
				for (int x2 = 0; x2 < xp[j].size(); x2++) {
					if (xp[j][x2] < y[k]) h++;
				}
				for (int y1 = 0; y1 < yp[k].size(); y1++) {
					int up = max(x[i], x[j]);
					int down = min(x[i], x[j]);
					if (yp[k][y1] < up && yp[k][y1] > down)
						s++;
				}
				ans = max(ans, h + s - Min + g[i][k] + g[j][k]);
				Min = min(Min, h - s);
				
			}
		}
	}
	return ans;
}

int main() {
	int cas = 0;
	while (~scanf("%d", &n) && n) {
		init();
		printf("Case %d: %d\n", ++cas, solve());
	}
	return 0;
}