Chainsaw Massacre

Chainsaw Massacre

时间: 1ms        内存:64M

描述:

The Canadian Lumberjack Society has just held its annual woodcutting competition and the national forests between Montreal and Vancouver are devastated. Now for the social part! In order to lay out an adequate dance floor for the evening party the organizing committee is looking for a large rectangular area without trees. All lumberjacks are already drunk and nobody wants to take the risk of having any of them operate a chainsaw.

The organizing committee has asked you to find the largest free rectangular region which can serve as the dance floor. The area in which you should search is also rectangular and the dance floor must be entirely located in that area. Its sides should be parallel to the borders of the area. The dance floor may be located at the borders of the area, and trees may grow on the borders of the dance floor.

输入:

The first line of the input specifies the number of scenarios. For each scenario, the first line provides the length l and width w of the area in meters ( 0 < l, w<=10, 000, both integers). Each of the following lines describes either a single tree, or a line of trees according to one of the following formats: 1 x y, where the ``1'' characterizes a single tree, and x and y provide its coordinates in meters with respect to the upper-left corner. k x y dx dy, where k > 1 provides the number of trees in a line with coordinates (x, y),(x + dx, y + dy),...,(x + (k - 1)dx, y + (k - 1)dy).
0 denotes the end of the scenario.
The coordinates x, y, dx, and dy are given as integers. All the trees will be situated in this area, i.e., have coordinates in [0, l] x [0, w]. There will be at most 1,000 trees.

输出:

For each scenario print a line containing the maximum size of the dance floor measured in square meters.

示例输入:

2
2 3
0
10 10
2 1 1 8 0
2 1 9 8 0
0

示例输出:

6
80

提示:

参考答案(内存最优[1488]):

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int T;
	int l,w;
	int k,dx,dy;
	int x[10001],y[10001];
	int area;
	int area_x,area_y;
	int max_x,max_y;
	int i;
	int dis_x,dis_y;
	cin>>T;
	while(T--)
	{
		cin>>l>>w;
		area=l*w;
		i=0;
		while(cin>>k)
        {
            if(!k)
            {
                break;
            }
            cin>>x[i]>>y[i]>>dx>>dy;
            i++;
            for(;i<k;i++)
            {
                x[i]=x[i-1]+dx;
                y[i]=y[i-1]+dy;
            }
        }
        k=i;
        if(!k)
        {
            cout<<area<<endl;
            continue;
        }
		sort(x,x+k);
		sort(y,y+k);
		dis_x=0;
		dis_y=0;
		max_x=0;
		max_y=0;
		if(k==1)
		{
			dis_x=x[0];
			dis_y=y[0];
			max_x=l-x[0];
			max_y=w-y[0];
			if(dis_x>max_x)
			{
				max_x=dis_x;
			}
			if(max_y<dis_y)
			{
				max_y=dis_y;
			}
		}
		else
		{
			for(i=0;i<k-1;i++)
			{
				dis_x=x[i+1]-x[i];
				dis_y=y[i+1]-y[i];
				if(dis_x>max_x)
				{
					max_x=dis_x;
				}
				if(dis_y>max_y)
				{
					max_y=dis_y;
				}
			}
		}
		area_x=max_x*w;
		area_y=max_y*l;
		area=area_x;
		if(area<area_y)
		{
			area=area_y;
		}
		cout<<area;
	}
	return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int T;
	int l,w;
	int k,dx,dy;
	int x[10001],y[10001];
	int area;
	int area_x,area_y;
	int max_x,max_y;
	int i;
	int dis_x,dis_y;
	cin>>T;
	while(T--)
	{
		cin>>l>>w;
		area=l*w;
		i=0;
		while(cin>>k)
        {
            if(!k)
            {
                break;
            }
            cin>>x[i]>>y[i]>>dx>>dy;
            i++;
            for(;i<k;i++)
            {
                x[i]=x[i-1]+dx;
                y[i]=y[i-1]+dy;
            }
        }
        k=i;
        if(!k)
        {
            cout<<area<<endl;
            continue;
        }
		sort(x,x+k);
		sort(y,y+k);
		dis_x=0;
		dis_y=0;
		max_x=0;
		max_y=0;
		if(k==1)
		{
			dis_x=x[0];
			dis_y=y[0];
			max_x=l-x[0];
			max_y=w-y[0];
			if(dis_x>max_x)
			{
				max_x=dis_x;
			}
			if(max_y<dis_y)
			{
				max_y=dis_y;
			}
		}
		else
		{
			for(i=0;i<k-1;i++)
			{
				dis_x=x[i+1]-x[i];
				dis_y=y[i+1]-y[i];
				if(dis_x>max_x)
				{
					max_x=dis_x;
				}
				if(dis_y>max_y)
				{
					max_y=dis_y;
				}
			}
		}
		area_x=max_x*w;
		area_y=max_y*l;
		area=area_x;
		if(area<area_y)
		{
			area=area_y;
		}
		cout<<area;
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注