Problem
open.kattis.com/problems/doors
vjudge.net/contest/183886#problem/B
Reference
点到线段的最短距离算法
Meaning
有两个球 Alex 和 Bob,问 Alex 要能通过障碍碰到 Bob,它最大的半径是多少。
Analysis
记o(0,w)
、a(l,w)
、d(l - l * cos(A),w + l * sin(A))
、b(l,0)
、e(l - l * cos(B),l * sin(B))
、c(3.0 * l,w)
(点c
是上面的右边那条射线上的一点),那么会卡住 Alex(限制 Alex 半径)的是:
1. R(原来的大小)
2. l / 2
3. w / 2(因题目保证
l≤w
,所以这条忽略)
4. 点 o 到线段 ad 的距离
5. 点 e 到线段 ad 的距离
6. 点 a 到线段 be 的剧离
7. 点 e 到线段 ac 的距离
所以是这几个值取最小。
Code
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double EPS = 1e-10;
// 浮点数的符号
int sgn(double f)
{
if(f < -EPS)
return -1;
if(f > EPS)
return 1;
return 0;
}
// 点、向量
typedef struct pnt // point
{
double x, y;
pnt(double _x = 0.0, double _y = 0.0):
x(_x), y(_y) {}
// 判相等
bool operator == (const pnt &rhs) const
{
return !sgn(x - rhs.x) && !sgn(y - rhs.y);
}
// 两点相减 -> 得出向量
pnt operator - (const pnt &rhs) const
{
return pnt(x - rhs.x, y - rhs.y);
}
// 向量点积
double operator * (const pnt &rhs) const
{
return x * rhs.x + y * rhs.y;
}
// 向量叉积(的模)
double operator ^ (const pnt &rhs) const
{
return x * rhs.y - rhs.x * y;
}
} vec; // vector
// VECtor LENgth -> 向量长
double veclen(const vec &v)
{
return sqrt(v * v);
}
// Point to Segment -> 点 p 到线段 ab 距离
double ps(const pnt &p, const pnt &a, const pnt &b)
{
if(a == b)
return veclen(p - a);
vec ab = b - a, ap = p - a, bp = p - b;
// 垂足在 a 点左边
if(sgn(ab * ap) < 0)
return veclen(ap);
// 垂足在 b 点右边
if(sgn(ab * bp) > 0)
return veclen(bp);
// 垂足在 ab 上
return fabs(ab ^ ap) / veclen(ab);
}
int main()
{
double R, l, w;
int T;
scanf("%lf%lf%lf%d", &R, &l, &w, &T);
while(T--)
{
double A, B;
scanf("%lf%lf", &A, &B);
pnt o(0.0, w), a(l, w), ua(l - l * cos(A), w + l * sin(A)),
c(l * 3.0, w), b(l, 0.0), ub(l - l * cos(B), l * sin(B));
double r = min(R, l / 2.0); // l <= w
r = min(r, ps(o, a, ua) / 2.0);
r = min(r, ps(ub, a, ua) / 2.0);
r = min(r, ps(ub, a, c) / 2.0);
r = min(r, ps(a, b, ub) / 2.0);
printf("%.9f\n", r);
}
return 0;
}