这题需要什么精巧的算法吗？
有没有什么极端测试数据。

我的代码基本就是把人脑的思路模拟了一下
每次找出可切的，然后根据题意选一条线切下去

#include<iostream>
#include <stdio.h>
#include<list>

using namespace std;


int N;


struct PT
{
	int x0,y0;

	int x1,y1;
	int x2,y2;

	int x3,y3;
}rect[2001];



struct PPT
{
	struct PT pt;

	int x1,x2,y1,y2;

	bool hhuos;
};

list<struct PPT> rlist;


void sort()
{
	int i, j;
	int l, k;
	struct PT tmp;


	for(i = 0;i < N;i++)
	{
		for(j = i + 1;j < N;j++)
		{
			if(rect[i].y0 > rect[j].y0)
			{
				tmp = rect[i];
				rect[i] = rect[j];
				rect[j] = tmp;
			}
			else
				if(rect[i].y0 == rect[j].y0 && rect[i].x0 > rect[j].x0)
				{
					tmp = rect[i];
					rect[i] = rect[j];
					rect[j] = tmp;
				}

		}
	}
}


void f(struct PPT &ppt)
{
	struct PT rt[2000], tmp;
	int num;

	int i;
	int j;
	int id;



	num = 0;

	for(i = 0;i < N;i++)
	{
		if(rect[i].x0 == ppt.pt.x0 && rect[i].y0 < ppt.pt.y0 && rect[i].y0 > ppt.pt.y1)
		{

			rt[num] = rect[i];

			num++;
		}
	}


	for(i = 0;i < num;i++)
	{

		for (j=0;j<N;j++) {
			if (rect[j].x3==ppt.pt.x3 && rect[j].y3==rt[i].y0)
				break;
		}
		if (j==N) continue;

		int x,y;
		bool flag;

		x = rt[i].x3;
		y = rt[i].y3;


		flag = false;

		while(1)
		{

			for(j = 0;j < N;j++)
			{
				if((y == rect[j].y0 && x == rect[j].x0 && x < ppt.pt.x3))// || (y == rect[j].y1 && x == rect[j].x1))
				{
					x = rect[j].x3;
					y = rect[j].y3;
					break;
				}
			}

			//if(j < N)
			//{
				if(x == ppt.pt.x3)
				{
					flag = true;
					break;
				}
			//}
				if (j==N )
					break;


		}

		if(flag == true)
		{
			ppt.x1 = rt[i].x0;
			ppt.y1 = rt[i].y0;

			ppt.x2 = x;
			ppt.y2 = ppt.y1;
			
			ppt.hhuos=false;

			//cout << "fu false\n";
			return;
		}

		else {
			//cout << "zhao bu dao";
		}	
	
	}




	num = 0;

	for(i = 0;i < N;i++)
	{
		if(rect[i].y0 == ppt.pt.y0 && rect[i].x0 > ppt.pt.x0 && rect[i].x0 < ppt.pt.x3)
		{

			rt[num] = rect[i];

			num++;
		}
	}

	for(i = 0;i < num;i++)
	{

		for (j=0;j<N;j++) {
			if (rect[j].x1==rt[i].x0 && rect[j].y1==ppt.pt.y1)
				break;
		}
		if (j==N) continue;

		int x,y;
		bool flag;

		x = rt[i].x1;
		y = rt[i].y1;


		flag = false;

		while(1)
		{

			for(j = 0;j < N;j++)
			{
				if((y == rect[j].y0 && x == rect[j].x0 && y>ppt.pt.y1))// || (y == rect[j].y1 && x == rect[j].x1))
				{
					x = rect[j].x1;
					y = rect[j].y1;
					break;
				}
			}

			//if(j < N)
			//{
				if(y == ppt.pt.y1)
				{
					flag = true;
					break;
				}
			//}
				if (j==N)
					break;


		}

		if(flag == true)
		{
			ppt.x1 = rt[i].x0;
			ppt.y1 = rt[i].y0;

			ppt.x2 = x;
			ppt.y2 = y;
			
			ppt.hhuos=true;

			//cout << "fu true\n";
			return;
		}

		else {
			//cout << "zhao bu dao";
		}
	
	}

	if (num==0) {
		ppt.x1=10000;
	}

}

void findmaxrect()
{
	int i;
	int minx;
	int miny;
	int maxx;
	int maxy;

	struct PPT r;

	minx = 10000;
	miny = 10000;
	maxx = -10000;
	maxy = -10000;

	for(i = 0;i < N;i++)
	{
		if(rect[i].x1 < minx)
			minx = rect[i].x1;

		if(rect[i].y1 < miny)
			miny = rect[i].y1;

		if(rect[i].x3 > maxx)
			maxx = rect[i].x3;

		if(rect[i].y3 > maxy)
			maxy = rect[i].y3;	
	}

	r.pt.x0 = minx;
	r.pt.y0 = maxy;

	r.pt.x1 = minx;
	r.pt.y1 = miny;

	r.pt.x2 = maxx;
	r.pt.y2 = miny;

	r.pt.x3 = maxx;
	r.pt.y3 = maxy;

	f(r);

	rlist.push_back(r);

}


void solve()
{
	int i;
	int minx;
	int id;
	int k;

	list<struct PPT>::iterator p, idd;
	idd=rlist.begin();


	for(k = 0;k < N - 1;k++)
	{

		idd=rlist.begin();
		for(p =rlist.begin();p != rlist.end();p++)
		{

			//if(rlist[i].x1 < minx)
			//{
			//	minx = rlist[i].x1;
			//	id = i;
			//}

			if(p->x1 < idd->x1 || (p->x1 == idd->x1 && p->y2 < idd->y2))
			{
				//minx = p->x1;

				idd = p;
			}


		}

		cout << idd->x1 << ' ' << idd->y2 << ' ' << idd->x2 << ' ' << idd->y1 << endl;

		int x10, y10, x11, y11, x12, y12, x13, y13;
		int x20, y20, x21, y21, x22, y22, x23, y23;

		x10 = idd->pt.x0;
		y10 = idd->pt.y0;

		if(idd->hhuos == false)
		{
			x11 = idd->x1;
			y11 = idd->y1;

			x12 = idd->x2;
			y12 = idd->y2;

			x13 = idd->pt.x3;
			y13 = idd->pt.y3;

		}
		else
		{
			x11 = idd->pt.x1;
			y11 = idd->pt.y1;

			x12 = idd->x2;
			y12 = idd->y2;

			x13 = idd->x1;
			y13 = idd->y1;

		}






		

		if(idd->hhuos == false)
		{
			x21 = idd->pt.x1;
			y21 = idd->pt.y1;

			x22 = idd->pt.x2;
			y22 = idd->pt.y2;

			x23 = idd->x2;
			y23 = idd->y2;


			x20 = idd->x1;
			y20 = idd->y1;

		}
		else
		{
			x20 = idd->x1;
			y20 = idd->y1;

			x21 = idd->x2;
			y21 = idd->y2;

			x22 = idd->pt.x2;
			y22 = idd->pt.y2;

			x23 = idd->pt.x3;
			y23 = idd->pt.y3;

		}

		struct PPT ppt1, ppt2;

		ppt1.pt.x0 = x10;
		ppt1.pt.y0 = y10;

		
		ppt1.pt.x1 = x11;
		ppt1.pt.y1 = y11;

		ppt1.pt.x2 = x12;
		ppt1.pt.y2 = y12;

		ppt1.pt.x3 = x13;
		ppt1.pt.y3 = y13;


		ppt2.pt.x0 = x20;
		ppt2.pt.y0 = y20;

		
		ppt2.pt.x1 = x21;
		ppt2.pt.y1 = y21;

		ppt2.pt.x2 = x22;
		ppt2.pt.y2 = y22;

		ppt2.pt.x3 = x23;
		ppt2.pt.y3 = y23;

		f(ppt1);

		f(ppt2);

		rlist.erase(idd);

		if (ppt1.x1!=10000)
			rlist.push_back(ppt1);
		if (ppt2.x1!=10000)
			rlist.push_back(ppt2);
	}
}


main()
{
	int i;

	while(true) {
		cin >> N;
		if (N==0) return 0;

		for(i = 0;i < N;i++) {
			//cin >> rect[i].x1 >> rect[i].y1 >> rect[i].x3 >> rect[i].y3;
			scanf("%d %d %d %d",&rect[i].x1,&rect[i].y1,&rect[i].x3,&rect[i].y3);
			rect[i].x0=rect[i].x1;
			rect[i].y0=rect[i].y3;
			rect[i].x2=rect[i].x3;
			rect[i].y2=rect[i].y1;
		}

		sort();

		findmaxrect();

		solve();
		cout << endl;
	}



}

• 用这么长的代码吗？算法不太对吧！ (6892) tide713 2005-05-01 15:45:58