HDU 5572--An Easy Physics Problem(射线和圆的交点)
HDU 5572--An Easy Physics Problem(射线和圆的交点)
An Easy Physics Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3840 Accepted Submission(s): 765
Problem Description On an infinite smooth table, there’s a big round fixed cylinder and a little ball whose volume can be ignored.
Currently the ball stands still at point A, then we’ll give it an initial speed and a direction. If the ball hits the cylinder, it will bounce back with no energy losses.
We’re just curious about whether the ball will pass point B after some time.
Input First line contains an integer T, which indicates the number of test cases.
Every test case contains three lines.
The first line contains three integers Ox, Oy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.
The second line contains four integers Ax, Ay, Vx and Vy, indicating the coordinate of A is (Ax,Ay) and the initial direction vector is (Vx,Vy).
The last line contains two integers Bx and By, indicating the coordinate of point B is (Bx,By).
⋅ 1 ≤ T ≤ 100.
⋅ |Ox|,|Oy|≤ 1000.
⋅ 1 ≤ r ≤ 100.
⋅ |Ax|,|Ay|,|Bx|,|By|≤ 1000.
⋅ |Vx|,|Vy|≤ 1000.
⋅ Vx≠0 or Vy≠0.
⋅ both A and B are outside of the cylinder and they are not at same position.
Output For every test case, you should output “Case #x: y”, where x indicates the case number and counts from 1. y is “Yes” if the ball will pass point B after some time, otherwise y is “No”.
Sample Input 2 0 0 1 2 2 0 1 -1 -1 0 0 1 -1 2 1 -1 1 2
Sample Output Case #1: No Case #2: Yes
Source 2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工）
先判断射线和圆交点个数，如果小于2再看是否B在A的前进方向上，没有则NO，否则YES。如果等于2，就先找到第一个交点，将这个交点和圆心连成直线，那么A的路径关于这条直线对称，那么如果A关于此直线的对称点在圆心->B路径上，则可以相撞，否则不行。 这里有一个小问题，如果反过来求B关于此直线的对称点在圆心->A路径上，是会WA的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const double eps = 1e-8;
int sgn(double x) {
if (fabs(x) < eps)return 0;
if (x < 0)return -1;
else return 1;
}
struct point {
double x, y;
point() {}
point(double x, double y) : x(x), y(y) {}
void input() {
scanf("%lf%lf", &x, &y);
}
bool operator ==(point b)const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator <(point b)const {
return sgn(x - b.x) == 0 ? sgn(y - b.y)<0 : x<b.x;
}
point operator -(const point &b)const { //返回减去后的新点
return point(x - b.x, y - b.y);
}
point operator +(const point &b)const { //返回加上后的新点
return point(x + b.x, y + b.y);
}
point operator *(const double &k)const { //返回相乘后的新点
return point(x * k, y * k);
}
point operator /(const double &k)const { //返回相除后的新点
return point(x / k, y / k);
}
double operator ^(const point &b)const { //叉乘
return x*b.y - y*b.x;
}
double operator *(const point &b)const { //点乘
return x*b.x + y*b.y;
}
double len() { //返回长度
return hypot(x, y);
}
double len2() { //返回长度的平方
return x*x + y*y;
}
point trunc(double r) {
double l = len();
if (!sgn(l))return *this;
r /= l;
return point(x*r, y*r);
}
};
struct line {
point s;
point e;
line() {
}
line(point _s, point _e) {
s = _s;
e = _e;
}
bool operator ==(line v) {
return (s == v.s) && (e == v.e);
}
//返回点p在直线上的投影
point lineprog(point p) {
return s + (((e - s)*((e - s)*(p - s))) / ((e - s).len2()));
}
//返回点p关于直线的对称点
point symmetrypoint(point p) {
point q = lineprog(p);
return point(2 * q.x - p.x, 2 * q.y - p.y);
}
//点是否在线段上
bool pointonseg(point p) {
return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s)*(p - e)) <= 0;
}
};
struct circle {//圆
double r; //半径
point p; //圆心
void input() {
p.input();
scanf("%lf", &r);
}
circle() { }
circle(point _p, double _r) {
p = _p;
r = _r;
}
circle(double x, double y, double _r) {
p = point(x, y);
r = _r;
}
//求直线和圆的交点，返回交点个数
int pointcrossline(line l, point &r1, point &r2) {
double dx = l.e.x - l.s.x, dy = l.e.y - l.s.y;
double A = dx*dx + dy*dy;
double B = 2 * dx * (l.s.x - p.x) + 2 * dy * (l.s.y - p.y);
double C = (l.s.x - p.x)*(l.s.x - p.x) + (l.s.y - p.y)*(l.s.y - p.y) - r*r;
double del = B*B - 4 * A * C;
if (sgn(del) < 0) return 0;
int cnt = 0;
double t1 = (-B - sqrt(del)) / (2 * A);
double t2 = (-B + sqrt(del)) / (2 * A);
if (sgn(t1) >= 0) {
r1 = point(l.s.x + t1 * dx, l.s.y + t1 * dy);
cnt++;
}
if (sgn(t2) >= 0) {
r2 = point(l.s.x + t2 * dx, l.s.y + t2 * dy);
cnt++;
}
return cnt;
}
};
point A, V, B;
circle tc;
point r1, r2;
int main() {
int t, d = 1;
scanf("%d", &t);
while (t--) {
tc.input();
A.input();
V.input();
B.input();
int f = 0;
int num = tc.pointcrossline(line(A, A + V), r1, r2);
if (num < 2) {
point t = B - A;
if (t.trunc(1) == V.trunc(1)) f = 1;
else f = 0;
}
else {
line l = line(tc.p, r1);
line l1 = line(A, r1);
line l2 = line(r1, B);
point t = l.symmetrypoint(A);
if (l1.pointonseg(B))f = 1;
else if (l2.pointonseg(t))f = 1; //求B的对称点会WA
else f = 0;
}
if (f == 1)
printf("Case #%d: Yes\n", d++);
else
printf("Case #%d: No\n", d++);
}
return 0;
}