P10562 [ICPC2024 Xi'an I] Triangle 题解

· · 题解

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;
}

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