> 这题需要什么精巧的算法吗？
> 有没有什么极端测试数据。
> 
> 我的代码基本就是把人脑的思路模拟了一下
> 每次找出可切的，然后根据题意选一条线切下去
> 
> #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;
> 	}
> 
> 
> 
> }
> 
>