0

在过去的几天里，我试图解决这个问题。我什至有解决方案，但我无法弄清楚。有人能帮我吗？

这里的问题：

给定平面上的两个矩形。两个矩形的中心都位于坐标原点（即矩形对称中心）。第一个矩形的边平行于坐标轴：平行于 Ox 轴的边长等于 w，平行于 Oy 轴的边长等于 h。第二个矩形可以通过将第一个矩形相对于坐标原点旋转角度α来获得。

示例：http: //i.imgur.com/qi1WQVq.png

你的任务是找到属于两个给定矩形的区域面积。该区域在图片中带有阴影。

输入 第一行包含三个整数 w, h, α (1 ≤ w, h ≤ 106; 0 ≤ α ≤ 180)。角度 α 以度为单位。

输出 在一行中打印一个实数 - 属于两个给定矩形的区域的面积。

如果其相对或绝对误差不超过 10 - 6，则该答案将被视为正确。

样本测试

输入 1 1 45 输出 0.828427125

输入 6 4 30 输出 19.668384925

这是一个可能的实现：

<?php
list($w, $h, $alphaInt) = explode(' ', '34989 23482 180');

if ($alphaInt == 0 || $alphaInt == 180) {
  $res = $h * $w;
}
else if ($alphaInt == 90) {
  $res = $h * $h;
}
else {
  if ($alphaInt > 90) $alphaInt = 180 - $alphaInt;

  $alpha = $alphaInt / 180.0 * M_PI;
  //echo '$alpha:' . $alpha . "\n";

  $cos = cos($alpha);
  $sin = sin($alpha);
  //echo '$cos:  ' . $cos . "\n";
  //echo '$sin:  ' . $sin . "\n";

  $c = $w / 2 * $cos + $h / 2 * $sin - $w / 2;
  //echo '$c:    ' . $c . "\n";

  $r1 = $c / $cos;
  $r2 = $c / $sin;
  //echo '$r1:   ' . $r1 . "\n";
  //echo '$r2:   ' . $r2 . "\n";

  $c = $w / 2 * $sin + $h / 2 * $cos - $h / 2;
  //echo '$c:    ' . $c . "\n";

  $r3 = $c / $cos;
  $r4 = $c / $sin;
  //echo '$r3:   ' . $r3 . "\n";
  //echo '$r4:   ' . $r4 . "\n";

  if ($r1 < 0 || $r2 < 0 || $r3 < 0 || $r4 < 0) {
    $res = $h * $h / $sin; //$res = $w * $w / $cos;
  }
  else {
    $res = $h * $w - $r1 * $r2 - $r3 * $r4;
  }
}

echo '$res:  ' . $res . "\n";
4

2 回答 2

0

小的alpha

当w*sin(alpha) < h*(1+cos(alpha))（即在新矩形的顶点第一次与旧矩形的顶点相交之前），相交的面积是原矩形（w * h）的面积减去4个三角形（2对相同的三角形）。设大三角形有斜边a，小三角形有斜边b，则面积为

A = w * h - a*a*cos(alpha)*sin(alpha) - b*b*cos(alpha)*sin(alpha)

原始矩形的边满足方程组：

a + a * cos(alpha) + b * sin(alpha) = w
a * sin(alpha) + b + b * cos(alpha) = h

使用半角公式，

a * cos(alpha/2) + b * sin(alpha/2) = w/(2*cos(alpha/2))
a * sin(alpha/2) + b * cos(alpha/2) = h/(2*cos(alpha/2))

因此（LHS 上的矩阵是一个旋转！）

a^2 + b^2 = (w^2 + h^2) / (2*cos(alpha/2))^2

和

A = h * w - (w^2 + h^2) * cos(alpha)* sin(alpha) / (2*cos(alpha/2))^2

（这可以进一步简化一点）

大alpha

当alpha更大（但仍然alpha<pi/2）时，交点是一个平行四边形（实际上是一个菱形），其 2 个高度h和 4 个边h/sin(alpha)，因此，h*h/sin(alpha)（是的，它不依赖于w！）

其他alpha

使用对称性将 alpha 减少到[0;pi/2]并使用上述两种情况之一。

于 2013-06-03T18:38:48.497 回答
0

您可以尝试将两个矩形都描述为四个线性不等式系统的解决方案。它们相交中的点集是两组线性不等式的解集。

您想要该组解决方案的区域。你可以找到你的八个不等式中至少有两个紧的所有点。过滤掉那些不满足所有不等式的。然后使用 Graham 的扫描获取他们的凸包，并使用测量员的公式计算面积。

此方法用于查找任何两个凸多边形的交点。稍作修改，它概括（以傅里叶-莫茨金消除的形式和用于计算体积计算的交点和行列式的双重描述方法）到任何维度的凸多面体。

于 2013-06-03T20:16:13.373 回答