3698012_ce.cc

北大大牛代码 1240道题的原代码 超级权威

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

using namespace std;

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

bool cmpx(node a, node b)
{
	return a.x < b.x;
}

bool cmpy(node a, node b)
{
	return a.y < b.y;
}

vector <int> num;

void solve()
{
	int i, j, k, l, c, s, q;
	int n1, n2;

	for (i = 0; i < n; i++)
	{
		s = i + 1;
		while (s < n && p[s].x == p[i].x)
		{
			s++;
		}
		n1 = s - i;
		if (n1 > max)
			max = n1;
		if (s == n)
		{
			break;
		}
		for (j = s + 1; j < n; j++)
		{
			k = j + 1;
			while (k < n && p[k].x == p[j].x)
			{
				k++;
			}
			n2 = k - j;
			c = 0;
			for (l = i; l < k; l++)
			{
				if (p[l].x == p[i].x || p[l].x == p[j].x)
					continue;
				tp[c++] = p[l];
			}
			if (c == 0)
			{
				if (n1 + n2 > max)
					max = n1 + n2;
				j = k - 1;
				continue;
			}
			sort(tp, tp + c, cmpy);
			int cnt;
			num.clear();
			for (l = 0; l < c; l++)
			{
				q = l + 1;
				cnt = 1;
				while (q < c && tp[q].y == tp[l].y)
					cnt++, q++;
				num.push_back(cnt);
				l = q - 1;
			}
			if (num.empty())
			{
				if (n1 + n2 > max)
					max = n1 + n2;
				j = k - 1;
				continue;
			}
			num.push_back(0);
			sort(num.begin(), num.end(), greater<int>());
			if (n1 + n2 + num.at(0) + num.at(1) > max)
				max = n1 + n2 + num.at(0) + num.at(1);
			j = k - 1;
		}
		i = s - 1;
	}
}

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

	while (scanf("%d", &n) == 1 && n != 0)
	{
		max = 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++, max);
	}
	return 0;
}