标签：ab frac 20230921 double 矩形 theta pi

20230921

T378733 成长 grow

思路

按题目模拟即可。

时空复杂度

时间：\(O(9)\)

空间：\(O(11)\)

T378729 清洁 clean

思路

首先我们可以将图分为上下两个矩形，以便于我们计算，然后我们会发现圆会和矩形有两个交点，而这两个交点分别会在两条边上，如下图（只有上半部分有）：

1. 
2. 
3. 
4. 

跟据图形，我们可以推出四种情况的特征：

设矩形高为 \(x\)，矩形底为 \(y\)，半径为 \(r\)（只有上半部分！）

1. r <= x && r <= y
2. r > x && r <= y
3. r <= x && r > y
4. r > x && r > y

那么我们就需要分类讨论，首先考虑情况 \(1\)：

1. 因为整个半圆都是包裹在矩形里的，所以可以直接用矩形面积减去半圆面积
2. 
   过点 \(b\) 做边 \(y\) 的垂线垂足为 \(c\)，根据三角函数：

\(\sin(\Theta) = \frac{a}{c}\)

在图中，即为 \(\sin(\theta)=\frac{bc}{ab}\) 变成反三角函数即为 \(\arcsin(\frac{bc}{ab})=\theta\)，通过公式可以算出角度，注意这里的角度单位是 \(\frac{180^\circ}{\pi}\)，所以要除以 \(2\pi\)，算出角度后就可以算出那个扇形的面积，最后加上一旁的三角形即可。
3. 依此类推即可
4.

由于 \(abc\) 构成不了一个直角三角形，也就不能通过 \(abc\) 来算 \(\theta\)，所以要用减法来计算，过 \(b\) 做边 \(y\) 垂线，垂足为 \(d\)，连接 \(ab, ac\)，可知：\(\beta = arcsin(\frac{bd}{ab})\)，还可知：\(\alpha = arccos(\frac{ae}{ac})\)，所以 \(\theta=\beta-\alpha=arcsin(\frac{bd}{ab})-arccos(\frac{ae}{ac})\)，算出 \(\theta\) 就和上面一样了，不过记得要算上下两个三角形。

code

#include <cmath>
#include <iostream>

using namespace std;

const double pi = 3.141593;

double H, W, h, R;

double solve(double x, double y, double r) {
  if (r * r >= x * x + y * y) {
    return x * y;
  }
  if (r <= x && r <= y) {
    return pi * r * r / 4;
  } else if (r <= x && r > y) {
    double t = sqrt(r * r - y * y), o = asin(y / r);
    return t * y / 2 + (o / (pi * 2)) * pi * r * r;
  } else if (r > x && r <= y) {
    double t = sqrt(r * r - x * x), o = asin(x / r);
    return t * x / 2 + (o / (pi * 2)) * pi * r * r;
  } else {
    double o = asin(x / r), o1 = acos(y / r), o2 = o - o1, t = sqrt(r * r - y * y), t1 = sqrt(r * r - x * x);
    return t * y / 2 + t1 * x / 2 + (o2 / (pi * 2)) * pi * r * r;
  }
}

int main() {
  cin >> H >> W >> h >> R;
  printf("%.4f", H * W - solve(h, W, R) - solve(H - h, W, R));
  return 0;
}

T378738 燃烧 burn

思路

可以考虑最右上角的位置，然后统计当前点可能会被那些点影响：

000000

对于最后一的点，它显然只能被自己覆盖，所以为 1

000001

对于倒数第二个点，它不仅能被自己覆盖，也能被最后一个点覆盖，所以为 0。

000001

依此类推，可以得到最后这一层将会变成

010101

考虑它的下一层，按同理可以推出：

010101
000000

所以最终会是一个：

010101
000000
010101
000000
……

那么如果说有一个矩阵的 \(1\) 的数量为 \(k\)，那么就会有 \(4\) 种可能：

1. 只有那个矩阵
2. 矩阵向下扩展（只扩展一层）
3. 矩阵向左扩展（只扩展一列）
4. 都扩展（只扩展一）

为什么只扩展一呢？因为在枚举的时候我们是枚举有 \(1\) 的层数，但是如果扩展多层，那么枚举的值会发生变化，就不属于这种矩阵的管辖了。

code

#include <iostream>

using namespace std;

const int mod = 998244353;

long long ans, n, m, k, x, y;

int main() {
  cin >> n >> m >> k;
  for (int i = 1; i <= (n + 1) / 2; i++) {
    if (k % i == 0 && k / i <= (m + 1) / 2) {
      int j = k / i, x = 2 * i - 1, y = j * 2 - 1;
      ans = (ans + 1ll * (n - x + 1) * (m - y + 1) % mod) % mod;
      ans = (ans + 1ll * (n - x) * (m - y) % mod) % mod;
      ans = (ans + 1ll * (n - x + 1) * (m - y) % mod) % mod;
      ans = (ans + 1ll * (n - x) * (m - y + 1) % mod) % mod;
    }
  } 
  cout << ans << endl;
  return 0;
}

时空复杂度

时间：\(O(n)\)

空间：\(O(n)\)

标签：ab,frac,20230921,double,矩形,theta,pi
From： https://www.cnblogs.com/ybtarr/p/17721955.html