Shanghai 2006/UV 1382 Distant Galaxy(エニュメレーション&スキャン&ダイナミックメンテナンス)

1382-Distant Galaxy
Time limit：3.000 seconds 
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=460&page=show_problem&problem=4128
You are observing a distant galaxy using a telescope above the Astronomy Tower，and You think that a rectanle drawn in that galaxy whose edges ars are e to coordiaxes and containmystem theemens。thus you have written the coordinans of all star system down a piece of paper and decide to work the relt later.Can You finish this task？
Input 
The re are multile test cases in the input file.Each test case starts with one integer N，（1 N 100），the number of star system on the telescope.N line follow，each line consists of ts of two integers：the mystratwo the the soreamement theand you can assiume that the plannets arbitrrily distributed in the universe.
N=0 indicates the end of input file and shound not be processed by your program.
Output 
For each test case，output the maximvalue you have found on a single line in the format as indicated in the sample out.
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

考え方:
長方形の上下を列挙して、左右の境界を選択します。確定された左境界のleftと右境界のrightについては、下図のR 3がleftであると仮定し、 L 3はrightで、数は：
L 1+L 2+L 3-(R 1+R 2)+R 3. 
L 3を右境界とする矩形上の点が最も多いようにするためには、R 3-（R 1＋R 2）の値が一番大きいはずである。
したがって、上下境界を列挙し、右境界jを列挙しながら、j左のR 3-（R 1＋R 2）の最大値を維持し、O(n^3)は答えを決定する。
完全コード:

/*0.025s*/

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 105;

struct Point
{
	int x, y;
	bool operator < (const Point& rhs) const
	{
		return x < rhs.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; //      y     
	if (m <= 2) return n; //   ，       y
	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]; //          ymin ymax   
			//   left, on, on2
			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] = (k == 0 ? 0 : 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; //   ，       x
			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]);//   ，    on[j] - left[j]
			}
		}
	return ans;
}

int main()
{
	int kase = 0;
	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
", ++kase, solve());
	}
	return 0;
}