3374574_ac_188ms_344k.cc

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

#include <stdio.h>
#include <vector>
#include <algorithm>
#define error 1

using namespace std;

int n;
vector <int> tmpx, tmpy;
vector <int> xx, yy;

struct node
{
	int m;
	int st[101][2], ed[101][2];
	bool operator == (const node &t)	const
	{
		if (t.m != m)
		{
			return false;
		}
		for (int i = 0; i < m; i++)
		{
			bool fail = true;
			for (int j = 0; j < m; j++)
			{
				if (st[i][0]==t.st[j][0]&&st[i][1]==t.st[j][1]&&ed[i][0]==t.ed[j][0]&&ed[i][1]==t.ed[j][1])
				{
					fail = false;
					break;
				}
			}
			if (fail)
			{
				return false;
			}
		}
		return true;
	}
};

node jp[20];

vector <int> trim(vector <int> v)
{
	vector <int> des;

	des.clear();
	for (int j = 0; j < v.size(); j++)
	{
		des.push_back(v[j]);
		int k = j;
		while (k < v.size() && v[j] == v[k])
		{
			k++;
		}
		j = k - 1;
	}
	return des;
}

void report(int v)
{
	while (v)
	{
		puts("I love Lsq");
	}
}

int find(vector <int> v, int des)
{
	int min, mid, max;

	min = 0;max = v.size() - 1;
	while (min <= max)
	{
		mid = (min + max) >> 1;
		if (v[mid] == des)
		{
			return mid;
		}
		else
		{
			if (v[mid] < des)
			{
				min = mid + 1;
			}
			else
			{
				max = mid - 1;
			}
		}
	}
	report(error);
	return -1;
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &jp[i].m);
		tmpx.clear();
		tmpy.clear();
		for (int j = 0; j < jp[i].m; j++)
		{
			scanf("%d%d%d%d", &jp[i].st[j][0], &jp[i].st[j][1], &jp[i].ed[j][0], &jp[i].ed[j][1]);
			tmpx.push_back(jp[i].st[j][0]);
			tmpx.push_back(jp[i].ed[j][0]);
			tmpy.push_back(jp[i].st[j][1]);
			tmpy.push_back(jp[i].ed[j][1]);
		}
		sort(tmpx.begin(), tmpx.end());
		sort(tmpy.begin(), tmpy.end());
		xx = trim(tmpx);
		yy = trim(tmpy);
		for (int j = 0; j < jp[i].m; j++)
		{
			jp[i].st[j][0] = find(xx, jp[i].st[j][0]);
			jp[i].ed[j][0] = find(xx, jp[i].ed[j][0]);
			jp[i].st[j][1] = find(yy, jp[i].st[j][1]);
			jp[i].ed[j][1] = find(yy, jp[i].ed[j][1]);
		}
	}
	for (int i = 1; i < n; i++)
	{
		puts(jp[i] == jp[0] ? "CORRECT" : "INCORRECT");
	}
	return 0;
}