自动搬运

查看原文

来自洛谷，原作者为

	Cypher_404 答应你们，1k 粉女装

搬运于2025-08-24 22:59:12，当前版本为作者最后更新于2024-06-02 15:34:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10562 [ICPC2024 Xi'an I] Triangle 题解

终于，第 5 篇了。

分析题意

题目给出 $A$ 的坐标：$(a,0)$，和 $B$ 的坐标：$(0,b)$，再加上已知的原点 $O$：$(0,0)$。

这三个点构成了一个直角三角形，需要你求出有多少个正方形在其中。（不足一个的如果占到了面积的 $50\%$ 及以上算，否则不算）。

分析做法

看到 $1 \le a,b \le 10^6$ 并不大，可以考虑暴力模拟。

具体模拟思路：

算出直线 $AB$ 的解析式，算出每一个的 $x$ 坐标所对应的 $y$，然后使用梯形面积公式（上底加下底的和除以 2）。

看到面积 $\ge 50\%$ 考虑四舍五入。

四舍五入：给浮点数类型的数字加上 $0.5$ 再强制转化成整形即可。可自行模拟检验。

坑点：

1. 卡精度：可以用 double 类型再乘上一个浮点数，如：$1.0000$。

2. 读题不仔细或思考不全：答案可能会爆 int，$\frac {10^6 \times 10^6} {2}$ 达到了惊人的 $5\times 10^{11}$ 必须使用 long long。

Code:

#include<bits/stdc++.h>
using namespace std;
double k,n,m;//浮点数类型
long long ans;//答案：可能会炸 int
double opt=1.00000;//乘数，减小精度误差
int main()
{
    cin>>n>>m;
    k=n*opt/-m;//计算 k
    for(int i=0;i<(int)m;i++)//从 1~m，虽然不加 (int) 也可以
    {
        double t=n+(2*i+1)*k/2;//简化以后的梯形公式
        t+=0.5;//四舍五入
        ans+=(long long)t;//强制转换成 long long 类型。实测：转换成 int 也可以。
    }
    cout<<ans;//输出
    return 0;
}

其实还是比较简单的一道题，希望大家多多点赞。