#include <iostream>
//#include <algorithm>
//#include <fstream>
using namespace std;

struct Col
{
	int value;
	int row;
};

struct Grid
{
	int value;
	int wall;
};

int QSCore(struct Col L[], int left, int right)
{
	int base = L[left].value;
	int temp = L[left].row;
	while (left < right)
	{
		while (L[right].value >= base && right > left) right--;
		L[left].value = L[right].value;
		L[left].row = L[right].row;
		while (L[left].value <= base && left < right) left++;
		L[right].value = L[left].value;
		L[right].row = L[left].row;
	}
	L[left].value = base;
	L[left].row = temp;
	return left;
}

void QS(struct Col L[], int left, int right)
{
	int middle;
	if (right > left)
	{
		middle = QSCore(L, left, right);
		QS(L, left, middle - 1);
		QS(L, middle + 1, right);
	}
}


int main()
{
	//data definition
	int t, n, k;
	struct Grid grid[120][120];
	int pass[120];
	struct Col col[120];
	int i, j, p, q, u, w, int_temp;
	int beginX, endX, beginY, endY;
	int maxX, maxY;
	int count;

	//input data
	//ifstream input("data.txt");
	cin >> t;
	for (w = 0; w < t; w++)
	{
		count = 0;
		cin >> n >> k;
		maxX = 0;
		maxY = 0;
		for (i = 0; i < 101; i++)
			for (j = 0; j < 101; j++)
			{
				grid[i][j].value = 0;
				grid[i][j].wall = -1;
			}
		for (i = 0; i < n; i++)
		{
			cin >> beginX >> beginY >> endX >> endY;
			if (beginX > endX) 
			{
				int_temp = beginX;
				beginX = endX;
				endX = beginX;
			}
			if (endX > maxX) maxX = endX;
			if (endY > maxY) maxY = endY;
			for (j = beginX; j <= endX; j++)
			{
				grid[endY][j].value = 1;
				grid[endY][j].wall = i;
			}
		}

		//scan grid to get value of pass
		for (i = 0; i <= maxX; i++)
		{
			pass[i] = 0;
			for (j = 0; j <= maxY; j++)
			{
				if (grid[j][i].value == 1) pass[i]++;
			}
		}

		//scan grid again
		for (i = 0; i <= maxX; i++)
		{
			if (pass[i] <= k) continue;
			for (j = 0; j <= maxY; j++)
			{
				col[j].row = j;
				if (grid[j][i].value == 0) col[j].value = 0;
				else
				{
					col[j].value = 1;
					for (p = i + 1; p <= maxX; p++)
					{
						if (grid[j][p].value == 1 && grid[j][p].wall == grid[j][i].wall) col[j].value++;
						else break;
					}
				}
			}

			QS(col, 0, maxY);

			for (p = maxY, j = pass[i]; j > k && p >= 0; j--, p--)
			{
				u = i + 1;
				q = col[p].row;
				while (grid[q][u].value == 1 && u <= maxX && grid[q][u].wall == grid[q][i].wall)
				{
					grid[q][u].value = 0;
					grid[q][u].wall = -1;
					pass[u]--;
					u++;
				}
				count++;		
			}
		}
		cout << count << endl;
	}
	return 0;
}

思路是这样子的:
>把所有点都用grid[][]记录，value值是墙为1，非墙为0;wall值记录属于哪一条墙的,若无墙则为-1
>从左往右遍历，
>如遇某列超出K了，假设超出M个
>在该列上选取对后面影响最大的M条墙，去除后
>继续遍历.
>去掉多少条墙，就是答案了。