Problem DescriptionWisKey的眼镜有500多度,所以眼神不大好,而且他有个习惯,就是走路喜欢看着地(不是为了拣钱哦),所以大家下次碰见他的时候最好主动打下招呼,呵呵.
但是Rabbit总是喜欢扮神秘,一天WisKey去食堂排队等着买饭,突然收到一道短消息,是Rabbit发的,”呵呵,又看见你了,你没看到我吧”.WisKey马上拉长脖子扫描食堂,可是就是看不到,再发短信问Rabbit在哪,Rabbit回信曰”我已经在寝室了”.WisKey无语....
假设食堂是个正方形,食堂中心坐标为(0,0),长度为2*L, WisKey保证在食堂内.
因为是吃饭高峰期,所以每个点上都站着人,当某些人处在同一直线上时就有可能被前面的人挡住.
聪明的ACMer请你帮帮WisKey,告诉他能不能看见Rabbit.
Input
输入L,sx,sy,px,py; L<=1000,sx,sy是WisKey的坐标,px,py是Rabbit的坐标.
以L=0为结束.
Output
对于每组输入数据,能看见输出”Yes”,看不见输出”No”.Rabbit不在食堂输出”Out Of Range”.
Sample Input`
5 0 0 1 1
5 0 0 2 0
5 0 0 6 6
5 0 0 -1 -1
0`
Sample Output`
Yes
No
Out Of Range
Yes`
分析:
刚开始以为只有上、下、左、右、左上、左下、右上、右下,这八个方向能够看见,然而发现自己还是太傻太天真。
首先这个点的横纵坐标必须的在[-n,n]这个范围之内,如果是在上、下、左、右这四个放下的话,则能看见的条件肯定就是一个为0,另一个为1.其余的情况的话,两个距离求最大公约数,如果再打公约数为1的话就能看见,否则看不见。
不懂得话可以用相似三角形的原理自己画一下
代码:
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int n , sx,sy,px,py,x,y,r;
while(~scanf("%d",&n)&&n)
{
scanf("%d%d%d%d",&sx,&sy,&px,&py);
if(px>n||py>n||px<-n||py<-n)//超出范围的
printf("Out Of Range\n");
else
{
x=abs(sx-px);
y=abs(sy-py);
if(x==0||y==0&&(x+y)!=1)//相当于在其上下左右这四个方向中的一个,必须满足一个为1,一个为0
{
printf("No\n");
continue;
}
r=x%y;
while(r!=0)
{
x=y;
y=r;
r=x%y;
}
if(y==1)//x,y为求得的两个点的横纵坐标的距离,只有当两个距离的最大公约数为1时,才能够看见
printf("Yes\n");
else printf("No\n");
}
}
return 0;
}