题目链接:uva 12508 - Triangles
in the Grid
题目大意:给出n,m,A和B,要求计算在(n+1)∗(m+1)的矩阵上,可以找出多少个三角形,面积在AB之间。
解题思路;首先枚举矩阵,然后计算有多少个三角形以该矩阵为外接矩阵,并且要满足体积在AB之间。然后对于每个矩阵,要确定在大的范围内可以确定几个。
枚举矩阵的内接三角形可以分为三类:
1.三角型的两点在一条矩阵边上的顶点,另一点在该边的对边上(不包括顶点)
2.以对角线为三角形的一边
这样可以枚举x,然后求出l和r,边界值。
3.三角形一点在矩形顶点上,另外两点在对应的边上
同样枚举x,但是这次x不能包括0和n(在情况2中计算过),对应红色三角形和蓝色三角形,面积减少x,所以可以根据这个计算满足的三角形个数。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll max(ll a, ll b) {
return a > b ? a : b;
}
inline ll min(ll a, ll b) {
return a < b ? a : b;
}
ll N, M, A, B;
ll solve (ll k) {
if (k < 0)
k = 0;
if (N > M)
swap(N, M);
ll ans = 0;
for (ll n = 1; n <= N; n++) {
for (ll m = 1; m <= M; m++) {
ll cnt = 0;
if (n * m <= k)
cnt += 2 * (n + m - 2);
ll l, r;
for (ll x = 0; x <= n; x ++) {
r = (m * x + k) / n;
if (r > m)
r = m;
ll t = m * x - k;
if(t <= 0)
l = 0;
else
l = (t - 1) / n + 1;
if(l <= r)
cnt += 2 * (r - l + 1);
}
for (ll x = 1; x < n; x++) {
ll tmp = n * m - x;
if (tmp <= k)
cnt += 4 * (m - 1);
else {
tmp = tmp - k;
ll u = m-1 - min(tmp / x + (tmp % x != 0), m-1);
cnt += 4 * u;
}
}
ans += cnt * (N - n + 1) * (M - m + 1);
}
}
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%lld%lld%lld%lld", &N, &M, &A, &B);
printf("%lld\n", solve(B*2) - solve(A*2-1));
}
return 0;
}
分享到:
相关推荐
MODELS which are used in videos or screenshots ARE NOT INCLUDED in package! You can use all post effects for monitor based visuals: Make security cams, crt monitors, led panels, night vision cameras ...
行业教育软件-学习软件-Triangles Rectangles Solver 1.2 英文版.zip
前端项目-triangles,Triangle background generator
NULL 博文链接:https://lengbingteng.iteye.com/blog/1769480
Velocity-Triangles-Kivy- 要求: Python版本3.7.1 库:Kivy == 1.11.1 kivymd == 0.104.1数学(包括Python)
Sierpinski与C-Turtle作者:Jan Pearce撰写的Python版本杰西·W·沃克(Jesse W.Walker)转换为C ++参考: 此仓库使用Jesse W.Walker的
var drawTriangles = require ( 'draw-triangles-2d' ) var path = [ [ 25 , 25 ] , [ 40 , 30 ] , [ 50 , 75 ] , [ 125 , 15 ] ] //get a thick polyline var mesh = require ( 'extrude-polyline' ) ( { ...
三角形网格元胞自动机和遗传算法的实验正在进行中的工作还不是很有趣去做打印高分显示顶部 DNA 序列
LoadShaders.cpp LoadShaders.o triangles triangles.frag triangles.vert LoadShaders.h Makefile triangles.cpp triangles.o 重新构建方法:make clean; make 运行方法:./triangles 另外,可以在同名博客网页...
js-三角形 带有 bdd 的 javascript
这是玩弄生成类似谢尔宾斯基垫圈的结果,部分用于数学课程项目。 用于计算三角形的方法相当简单: 如果采用具有 2^n^ 行的帕斯卡三角形并将偶数着色为白色,奇数为黑色,则结果是谢尔宾斯基三角形的近似值。...
OpenGL-ES-2.0-基本三角形和着色器- 通过构建自己的Android程序来构建基本的旋转三角和着色器,开始对OpenGL ES的理解。 这是在我自己的时间里建立的,历时一周。 使用 (第1课)作为我的程序的基础,但全部都是从头...
魔术三角形 使用 Javascript 和 Canvas,尝试重新创建 。
matlab最简单的代码3D坐标中两个三角形之间的最小距离 一组函数,可以计算MATLAB中3D空间中两个三角形之间的最小距离。 三角形定义为1x9 MATLAB数组,编码为[x1,y1,z1, x2,y2,z2, x3,y3,z3] ,即每个顶点3个笛卡尔...
我创建了这个迷你站点来练习 Javascript。... 该站点使用 JQuery 滑块来获得所需的谢尔宾斯基三角形复杂度级别,从 1(只有一个等边三角形)到 9 级深。 然后递归函数绘制分形图案。 基本情况是单个等边三角形,函数...
+ The scrollbar did not get reset to the top when the user read in a new data file. Fixed. + The structure of the code has been undergone some major changes to ease porting to Windows 95 and ...
- Displaying the number of vertices and triangles of the GameObject (can display the number including all children) - Change the colors of icons and labels - Displaying custom icon for any layer - ...
« ACM模板收集Let the ...4.the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal. 在这里记下一个重要的结论,一个生成树的有n各节点 可以用 n^(n-2)中生成树.
(Displaying Triangles) Write an app that displays the following patterns separately, one below the other. Use for loops to generate the patterns. All asterisks (*) should be displayed by a single ...