学步园

想死的心都有了，一只都不在状态啊今天！浪费时间浪费清楚，可耻！

不知道怎么的，内心好烦躁，一直静心不下来呀！算了，晚上好好刷题吧，昨天的一场比赛，自己什么都没做出来，看了解题报告觉得写的飘忽飘忽的真没意思，不如《算法竞赛》这本书上讲的好。所以，不会的题目我也懒得去学习了，还是学习这上面的知识点吧，但是真的有点慢，学的太慢，所以不行，还得加快速度。

描述一下这个题目，就是给出平面上n个点，找出一个矩形，使得边界上包含尽量多的点。

这个就可以引申，到矩形内有多少个点，等等矩形的问题。

解决方法呢，就是扫描，先把所有的信息存到结点内，然后按照y排序，当然你也可以按照x排序，扫描y。但是根据大体人的习惯，还是习惯扫描x的。所以就把y排序了，然后去重，求得，一共有多少个不重复的边，然后暴力所有的任意两条边，然后扫描次两条边的x。

这时候确定边上的点，就需要用到几个数组，比如说on，on2，还有left数组，left数组表明的是此线左边的线上的点，on代表的此线上的，并且不在两条y上面的点，而on2，表示此线上的点，并且包含在y上面的点，

那么left的递推公式就很容易得出了left[i] = left[i - 1] + on2[i] - on[i];

而总共的也就好表示了ans = left[j] + on2[j] - left[i] + on[i];

贴出代码,烦躁，学校的网老是不稳定！

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>

using namespace std;

const int MAXN = 100 + 11;

struct Point
{
	int x, y;
	bool operator < (const Point &t) const
	{
		return x < t.x;
	}
}p[MAXN];

int on[MAXN];

int on2[MAXN];

int left[MAXN];

int y[MAXN];

int N;

int solve()
{
	sort(p, p + N);
	sort(y, y + N);
	int 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];
			int 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] = 0;
					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 = 1;
	int a, b;
	while (scanf("%d", &N) != EOF)
	{
		if (N == 0)
		{
			break;
		}
		for (int i = 0; i < N; i++)
		{
			scanf("%d%d", &a, &b);
			p[i].x = a;
			p[i].y = b;
			y[i] = b;
		}
		int ans = solve();			
		printf("Case %d: %d\n", cas++, ans);
	}
//	system("pause");
	return 0;
}