题目描述
在二维坐标系中，所有的值是double类型，那么一个矩形可以由四个点来代表，(x1, y1)为最左的点，(x2, y2)为最上的点，(x3, y3)为最下的点，(x4, y4)为最右的点。给定4个点代表的矩形，再给定一个点(x, y)，判断(x, y)是否在矩形中
输入描述：
输入有五行，每行两个整数。
对于前四行，第i行的浮点数表示(
x
i
,
y
i
x_i, y_i
xi,yi)
最后一行两个浮点数表示(x, y)
输出描述：
若(x, y)在矩形中，输出"Yes"，否则输出"No"
示例1
输入
2.00 2.50
3.00 5.00
3.00 1.50
4.00 4.00
3.21 3.78
输出
Yes
示例2
输入
2.00 2.50
3.00 5.00
3.00 1.50
4.00 4.00
2333.33 2333333.33
输出
No
备注：
−
2
∗
1
0
10
⩽
x
i
,
y
i
,
x
,
y
⩽
2
∗
1
0
10
−2∗10^{10} \leqslant x_i,y_i,x,y \leqslant 2∗10^{10}
−2∗1010⩽xi,yi,x,y⩽2∗1010
保证输入的顺序与题目描述相同
解法一：
书上的解法，若矩形与横纵坐标轴不平行，则进行旋转。假设旋转角度为 θ ，则坐标旋转公式为：
{
x
′
=
x
∗
c
o
s
θ
+
y
∗
s
i
n
θ
y
′
=
y
∗
c
o
s
θ
−
x
∗
s
i
n
θ
\left\{ \begin{aligned} x^{'} & = x*cosθ + y*sinθ \\ y^{'} & = y*cosθ - x*sinθ \end{aligned} \right.
{x′y′=x∗cosθ+y∗sinθ=y∗cosθ−x∗sinθ
但是在计算 θ 的时候，需要用到开方，并且数据范围达到了
1
0
10
10^{10}
1010 。回想起17青岛网络赛某题，也是计算几何，也是
1
0
10
10^{10}
1010 范围，用 C++ 库函数 sqrt 直接 wa 了 63 发，换着法调精度，过早开始炼丹侠2333。。。最后换 java 才过。后来知道 sqrt 在
1
0
10
10^{10}
1010 左右会产生精度损失。。。同样的，这题如果用书上写法，最后一个测试数据过不了，我猜是因为精度问题。所以，写法中避免涉及到开方操作吧2333。。。
解法二：
叉积。只涉及到乘法和减法，相比较解法一，基本没啥精度损失。
关于向量叉积，有一个定理： 若 p1p0 和 p2p0 的叉积大于 0 ，说明 p1 在 p2 顺时针方向
于是我们可以依次判断：x1x2与x1x，x2x4与x2x，x4x3与4x，x3x1与x3x，若这四个叉积均大于 0 ，说明点在矩形内。
解法二代码：
#include <cstdio>
using namespace std;
double x[5], y[5];
inline double cross_product( int i, int j, int k ) {
return (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]);
}
void solve() {
bool flag = false;
if ( cross_product(0, 4, 1) > 0 && cross_product(1, 4, 3) > 0 &&
cross_product(3, 4, 2) > 0 && cross_product(2, 4, 0) > 0 )
puts("Yes");
else puts("No");
}
int main(void) {
for ( int i = 0; i < 5; ++i ) scanf("%lf%lf", x + i, y + i);
solve();
return 0;
}
