题目链接

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; }
05-11 14:03