首页 > 试题广场 >

格点三角形

[编程题]格点三角形
  • 热度指数：364 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛最近在研究三角形计数问题。
它认为，满足以下三个条件的三角形是“好三角形”。
1. 三角形的三个顶点均为格点，即横坐标和纵坐标均为整数。
2. 三角形的是直角三角形，且两条直角边平行于 x 轴和 y 轴 。
honoka想知道，在平面中选取一个大小为 的矩形格点阵，可以找到多少个不同的“好三角形”？由于答案可能过大，请对 1000000007 取模。
示例1

输入

2,3

输出

12

说明

如上图，共有2行3列格点。面积为0.5的直角三角形有8个：ABD、ABE、ADE、BDE、BCE、BCF、BEF、CEF。
如上图，面积为1的直角三角形有4个：ACD、ADF、ACF、DCF
因此共有12个符合条件的直角三角形。
请注意，ACE和BDF虽然也是直角三角形，但由于直角边并不是平行于 x 轴或 y 轴，所以并不合法 。
算法知识视频讲解
添加回答
Python3
牛客808686245号头像 牛客808686245号 
class Solution:
    def getNums(self , n: int, m: int) -> int:
        return (m*n*(m-1)*(n-1))%(10**9+7)

发表于 2022-09-23 22:23:35 回复(0)
几号发货头像 几号发货

解题思路:

  1. 描述:任意两条平行网格上选取3个不同时在一条线上的点都能构成符合题意的三角形,而且不存在某个三角形解不满足上述.因此上面描述提到的所有组合就是本题答案
  2. 先考虑行,这种选择有C(n,2)种选择,在仅含有2点的边选择2不同点有C(m,2),此时三角形第3点有2种选择
  3. 列同理,组合解便是C(n,2)*C(m,2)*2+C(m,2)*C(n,2)*2
发表于 2022-11-16 18:11:58 回复(0)
提交观点

问题信息

基础数学
难度：
2条回答 1068浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号