首页 > 试题广场 >

格点三角形

[编程题]格点三角形
  • 热度指数：366 时间限制：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 轴，所以并不合法 。
算法知识视频讲解
开通博客
头像 哈哈哈哈哈HA
发表于 2024-01-05 10:05:48
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回满足条件的格点直角三角形数量 * @param n int整型 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客494732号
发表于 2023-05-23 10:19:21
package main //import "fmt" /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回满足条件的格点直角三角形数量 * @param n int整型 格点的行数 * @param m int整型 格点的列数 * @re 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 氯化钠哈哈哈
发表于 2024-01-13 18:25:05
个人思路： 场景1：当高为1，宽为n时 计算： 固定(0,0)和(0,1)为边界 以(0,0),(0,1),(1,0)和(1,1)为顶点的区域内，符合要求的三角形有4个 以(0,0),(0,1),(2,0)和(2,1)为顶点的区域内，符合要求的三角形有4个 ... 以(0,0),(0,1 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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