简单几何
Typhoon
Time Limit:1000MS Memory Limit:65536K
Total Submit:43 Accepted:8
Description
Twilight's hometown, Fuzhou, Fujian's provincial capital, is attacked by a number of typhoons every summer.
Every time a typhoon comes, meteorological station will be issued warnings and forecast the typhoon moving line.
If a typhoon affected Fuzhou, twilight would have to stay at home, which made him very depressed.
Therefore, twilight uses the data released by the weather stations to forecast wether a typhoon would affect his home every time.
For simplicity, the map is considered as a two-dimensional plane,at the beginning the typhoon is located in (0,0) point, assuming that the typhoon's path is a straight line and keeps the same radius when it moves , if his home is just on the border of the typhoon he will not be affected.
Input
Each group of data includes five integers, x0, y0, x1, y1, R.
(x0, y0) is twilight's home's coordinates.
(x1, y1) is the direction vector of the typhoon.
R is the radius of typhoon.
-1000 <= X0, y0, x1, y1 <= 1000
x1^2+y1^2 ! = 0 ,0 <R <=500
Five 0 means input is end, you should not deal with this line of data.
Output
If the typhoon will affect the twilight's home, output Yes, otherwise No.
Print a blank line after each test case.
Sample Input
1 0 0 1 1
0 0 0 0 0
Sample Output
No
该题台风走的是一条射线，假设过原点由方向向量确定的直线为f(x,y),和f(x,y)垂直的直线为f’(x,y),我们分两种情况讨论:
1. 当点位于台风方向向量的相反方向,即在f’(x,y)的另一侧，如果点在以原点为圆心，r为半径的区域内(不包括边界),则受到影响，否则不受到影响.
因为f’(x,y)=x1*x+y1*y ,且当f’(x1,y1)* f’(x0,y0)<0时，（x1,y1）和（x0,y0）位于f’(x,y)的两侧。又因为f’(x1,y1)>0 ,所以本题之判断f’(x0,y0)<0即可
2. 当点位于台风方向向量的同一方向时，只要判断点到直线的距离是否小于r，小于的话就影响，否则不影响。又因为开方的速率要远远低于乘方，所以本题乘方后判断。
Source
/*
Problem:Typhoon
Author:Chad
Algrithem:(x1*y0+y1*x0)^2 >= r^2(x1^2+ y1^2)
Date:2009-11-25
*/
#include<iostream>
using namespace std;
int x0, y0, x1, y1,r;
int main()
{
int n=0;
while(cin>>x0>>y0>>x1>>y1>>r && !(!x0 && !y0 && !x1 && !y1 && !r))
{
if((n++)>0) cout<<endl;
//
if(x1*x0+y1*y0 < 0)
{
if(x1*x1+y1*y1>=r*r) cout<<"No\n";
else cout<<"Yes\n";
}
else if((x1*y0-y1*x0)*(x1*y0-y1*x0) >= r*r*(x1*x1+ y1*y1))
cout<<"No\n";
else
cout<<"Yes\n";
}
return 0;
}