uva 12508 - Triangles in the Grid(几何+计数)
题目链接：uva 12508 - Triangles in the Grid
题目大意：给出n，m。A和B。要求计算在(n+1)∗(m+1)的矩阵上。能够找出多少个三角形，面积在AB之间。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。解题思路；首先枚举矩阵。然后计算有多少个三角形以该矩阵为外接矩阵。而且要满足体积在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; }
