3699065_wa.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 203 行

#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <algorithm>

using namespace std;

int n, ans;
struct node
{
	int x, y;	
}p[100], tp[100];

bool cmpx(node one, node other)
{
	if (one.x == other.x)
	{
		return one.y < other.y;
	}
	else
	{
		return one.x < other.x;
	}
}

bool cmpy(node one, node other)
{
	return one.y < other.y;
}

vector <int> y;

int find1(int my)
{
	if (y.size() == 0)
		return 0;
	int min = 0, max = y.size(), mid;
	while (min < max)
	{
		mid = (min + max) >> 1;
		if (my <= y[mid])
			min = mid + 1;
		else
			max = mid - 1;
	}
	return min;
}

int find2(int my)
{
	if (y.size() == 0)
		return 0;
	int min = 0, max = y.size(), mid;
	while (min < max)
	{
		mid = (min + max) >> 1;
		if (my >= y[mid])
			min = mid + 1;
		else
			max = mid - 1;
	}
	return min;
}

void solve()
{
	int i, j, c, i1, i2;

	for (i1 = 0; i1 != n; ++i1)
	{
		for (i2 = i1; i2 != n; ++i2)
		{
			int x1 = p[i1].x;
			int x2 = p[i2].x;
			int y1 = p[i1].y;
			int y2 = p[i2].y;
			if (y1 > y2)
				swap(y1, y2);
			int cnt = 0;
			for (i = 0; i < n; i++)
			{
				if ((p[i].x == x1 || p[i].x == x2) && p[i].y <= y2 && p[i].y >= y1)
					cnt++;
			}
			int m;
			m = 0;
			y.clear();
			c = 0;
			for (i = 0; i < n; i++)
			{
				if (p[i].x == x1 || p[i].x == x2)
				{
					if (p[i].y > y2)
					{
						y.push_back(p[i].y);
					}
				}
				if (p[i].x < x2 && p[i].x > x1 && p[i].y >= y2)
				{
					tp[c++] = p[i];
				}
			}
			if (c == 0)
				m = y.size();
			else
			{
				int tmp;

				if (!y.empty())
				{
					sort(y.begin(), y.end());
				}
				sort(tp, tp + c, cmpy);
				for (i = 0; i < c; i++)
				{
					j = i + 1;
					while (j < c && tp[j].y == tp[i].y)
						j++;
					tmp = j - i;
					tmp += find1(tp[i].y);
					if (tmp > m)
						m = tmp;
					i = j - 1;
				}
			}
			cnt += m;
			m = 0;
			y.clear();
			c = 0;
			for (i = 0; i < n; i++)
			{
				if (p[i].x == x1 || p[i].x == x2)
				{
					if (p[i].y < y1)
					{
						y.push_back(p[i].y);
					}
				}
				if (p[i].x < x2 && p[i].x > x1 && p[i].y <= y1)
				{
					tp[c++] = p[i];
				}
			}
			if (c == 0)
				m = y.size();
			else
			{
				int tmp;

				if (!y.empty())
				{
					sort(y.begin(), y.end(), greater<int>());
				}
				sort(tp, tp + c, cmpy);
				for (i = 0; i < c; i++)
				{
					j = i + 1;
					while (j < c && tp[j].y == tp[i].y)
						j++;
					tmp = j - i;
					tmp += find2(tp[i].y);
					if (tmp > m)
						m = tmp;
					i = j - 1;
				}
			}
			cnt += m;
			if (y1 == y2)
			{
				for (i = 0; i < n; i++)
				{
					if (p[i].y == y1 && p[i].x < x2 && p[i].x > x1)
						cnt--;
				}
			}
			if (cnt > ans)
			{
				ans = cnt;
			}
		}
	}
}

int main()
{
	int i, cas = 1;

	while (scanf("%d", &n) == 1 && n != 0)
	{
		ans = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &p[i].x, &p[i].y);
		}
		sort(p, p + n, cmpx);
		solve();
		printf("Case %d: %d\n", cas++, ans);
	}
	return 0;
}