现在的位置: 首页 > 综合 > 正文

ZOJ 3534 Move the Mouse I (ZOJ Monthly, September 2011 F题)

2014年10月13日 ⁄ 综合 ⁄ 共 3689字 ⁄ 字号 评论关闭

题目连接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3534
解题思路:
Step1:判断小矩形初始状态和最后状态是否在大矩形内部,若是,则Step2,否则输出-1;
Step2:在旋转过程中,小矩形的所有点都不能跑到大矩形外边去,所以可以判定是否存在
小矩形的可旋转区域,即大矩形的每条边往内推进 r=sqrt((a/2)*(a/2)+(b/2)*(b/2)) 后,
是否存在一个矩形(可能退化为一个点),若存在,则Step3,否则输出-1;


Step3:存在小矩形的可旋转区(阴影部分),可以从图中看到大矩形被划分成了9部分;
设初始状态小矩形中心点为p1,最后状态小矩形中心点为p2,则:
1:两个点只要有一个在阴影内,则鼠标移动距离为两点的曼哈顿距离fabs(p1.x-p2.x)+fabs(p1.y-p2.y);
2:若两个点都在竖直线 x1 左边
  (1):只要有一个点在 B 区域,则作该点关于 x1 的对称点 temp1,则鼠标移动距离为 temp1 和另一点的曼哈顿距离;
  (2):两个点都在 A1 区域内,则将其中一个点先作关于 x1 的对称点 temp0,再作 temp0 关于水平线y2的对称点temp1, 则鼠标移动距离为 temp1 和另一点的曼哈顿距离;
  (3):两个点都在 A2 区域内 同(2)
  (4):一个点在 A1,一个点在 A2,则鼠标移动距离为fabs(p1.x-x1)+fabs(p2.x-x1)+fabs(p1.y-p2.y);
3:若两个点都在竖直线 x2 右边,讨论同2
4:若两个点都在水平线 y1 下边,讨论同2
5:若两个点都在水平线 y2 上边,讨论同2
6:两个点在 x1、x2、y1 或 y2 任意一条线的两端,鼠标移动距离为两点的曼哈顿距离fabs(p1.x-p2.x)+fabs(p1.y-p2.y);

这题同3536题类似,但3536题为鼠标可以任意方向移动,WA得死去活来,求大牛思路。。。。。。

 

AC代码:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<set>
using namespace std;
#define eps 1e-8
struct point
{
	double x,y;
	int state;
}p1,p2;
double length,width,a,b,r;
bool SpecialJudgeGoOn()
{
	if( p1.state == 1)
		if(p1.x+a/2>length || p1.x-a/2<0 || p1.y+b/2>width || p1.y-b/2<0)
			return false;
	if( p1.state == 2 )
		if(p1.x+b/2>length || p1.x-b/2<0 || p1.y+a/2>width || p1.y-a/2<0)
			return false;
	if( p2.state == 1)
		if(p2.x+a/2>length || p2.x-a/2<0 || p2.y+b/2>width || p2.y-b/2<0)
			return false;
	if( p2.state == 2 )
		if(p2.x+b/2>length || p2.x-b/2<0 || p2.y+a/2>width || p2.y-a/2<0)
			return false;
	return true;
}
int main()
{
	while(scanf("%lf%lf %lf%lf",&length,&width,&a,&b)!=EOF)
	{
		scanf("%lf%lf%d %lf%lf%d",&p1.x,&p1.y,&p1.state,&p2.x,&p2.y,&p2.state);
		r=sqrt((a/2)*(a/2)+(b/2)*(b/2));
		if( SpecialJudgeGoOn() )
		{
			if(p1.state == p2.state)
				printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
			else
			{
				double x1,x2,y1,y2;
				x1=r;	y1=r;
				x2=length-r;	y2=width-r;
				if(x1<=x2+eps && y1<=y2+eps)
				{
					if((p1.x>x1-eps && p1.x<x2+eps && p1.y>y1-eps && p1.y<y2+eps)
						|| (p2.x>x1-eps && p2.x<x2+eps && p2.y>y1-eps && p2.y<y2+eps))
						printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
					else if( p1.x<x1+eps && p2.x<x1+eps )
					{
						if(p1.y>y1-eps && p1.y<y2+eps)
						{
							p1.x=x1+x1-p1.x;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p2.y>y1-eps && p2.y<y2+eps)
						{
							p2.x=x1+x1-p2.x;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p1.y<y1+eps && p2.y<y1+eps)
						{
							p1.x=x1+x1-p1.x;
							p1.y=y1+y1-p1.y;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p1.y>y2-eps && p2.y>y2-eps)
						{
							p1.x=x1+x1-p1.x;
							p1.y=y2-(p1.y-y2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else
							printf("%.3lf\n",fabs(p1.x-x1)+fabs(p2.x-x1)+fabs(p1.y-p2.y));
					}
					else if( p1.x>x2-eps && p2.x>x2-eps)
					{
						if(p1.y>y1-eps && p1.y<y2+eps)
						{
							p1.x=x2-(p1.x-x2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p2.y>y1-eps && p2.y<y2+eps)
						{
							p2.x=x2-(p2.x-x2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p1.y<y1+eps && p2.y<y1+eps)
						{
							p1.x=x2-(p1.x-x2);
							p1.y=y1+y1-p1.y;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p1.y>y2-eps && p2.y>y2-eps)
						{
							p1.x=x2-(p2.x-x2);
							p1.y=y2-(p1.y-y2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else
							printf("%.3lf\n",fabs(p1.x-x2)+fabs(p2.x-x2)+fabs(p1.y-p2.y));
					}
					else if( p1.y<y1+eps && p2.y<y1+eps )
					{
						if(p1.x>x1-eps && p1.x<x2+eps)
						{
							p1.y=y1+y1-p1.y;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p2.x>x1-eps && p2.x<x2+eps)
						{
							p2.y=y1+y1-p2.y;
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else
							printf("%.3lf\n",fabs(p1.y-y1)+fabs(p2.y-y1)+fabs(p1.x-p2.x));
					}
					else if( p1.y>y2-eps && p2.y>y2-eps)
					{
						if(p1.x>x1-eps && p1.x<x2+eps)
						{
							p1.y=y2-(p1.y-y2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else if(p2.x>x1-eps && p2.x<x2+eps)
						{
							p2.y=y2-(p2.y-y2);
							printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
						}
						else
							printf("%.3lf\n",fabs(p1.y-y2)+fabs(p2.y-y2)+fabs(p1.x-p2.x));
					}
					else
						printf("%.3lf\n",fabs(p1.x-p2.x)+fabs(p1.y-p2.y));
				}
				else
					puts("-1");
			}
		}
		else
			puts("-1");
	}
	return 0;
}

 

抱歉!评论已关闭.