2025年【洛谷 11 月月赛 I & MCOI Round 3 Div.2】【数学】正方

科技前沿 • 2025-01-28 13:05 • 阅读 64

大家好，我是讯享网，很高兴认识大家。

传送门

题目背景

MC 中没有圆。

所以小 S 和小 Q 和小 U 和小 A 和小 R 和小 E 喜欢 Square。

题目描述

给定一个正方形，求有多少个正方形内的点满足与正方形四个顶点划分出来的四块面积的比为 $a : b : c : d$ 。四个数不分顺序。

比如如下图所示假设一个点E使得分成的四个三角形的面积之比为 $a : b : c : d$ ，那么这个点E就符合要求。因为不分顺序，所以分出来的比是 $d : b : a : c$ 也可以。但是点E不是唯一解，你要输出的是解的个数。

在这里插入图片描述
讯享网

因为小 S 和小 Q 和小 U 和小 A 和小 R 和小 E 很喜欢询问，所以本题给定了 $q$ 组询问。

输入格式

第一行一个整数 $q$ 代表询问个数。
接下来行每行四个整数 $a, b, c, d$ 。

输出格式

$q$ 行每行一个整数代表答案。

输入输出样例

输入 #1

3 1 3 3 1 2 4 7 8 2 3 1 4

讯享网

输出 #1

讯享网4 0 8

说明/提示

数据规模与约定

对于 $20\%$ 的数据， $a = b = c = d$ 。
对于 $100\%$ 的数据， $\le a,b,c,d \le 10^{18}$ ， $\le q \le 100$ ，不保证 $a : b : c : d$ 为最简比，不保证 $a, b, c, d$ 为升序。

解题思路

先用样例中的第四个举例

可以看出，划分出的三角形的面积和底没有关系，那么就是划分高，也就是说对着的两个三角的高加起来等于边长
那么三角形的比例就是高的比例，先按照和把4个高分成两组，而且两组高的和相等（1 + 4 = 2 + 3）
下图是其中一种解

在这里插入图片描述
先划分出2：3，再划分出1：4，两条划分线的交点就是答案
考虑划分2：3，有4种方案

划分1：4也有4种方案

所以咧，一共有4 + 4种方案

还要考虑一些特殊情况

3和3，就只有1种方案
1，1，3，3 两组相同，需要去重

Code

#include <algorithm> #include <iostream> #include <cstdio> using namespace std; int T, x, y, k; long long a[5]; int main(){ 
    scanf ("%d", &T); for (int i = 1; i <= T; i++) { 
    scanf ("%lld%lld%lld%lld", &a[1], &a[2], &a[3], &a[4]); sort (a + 1, a + 1 + 4);//我不管，我最懒，我就sort if (a[1] + a[4] != a[2] + a[3])//如果两组和不相等，就无法确认边长 { 
    printf ("0\n"); continue; } if (a[1] == a[4])//如果一组相同，那么就只有一种情况 x = 1; else x = 4; if (a[2] == a[3]) y = 1; else y = 4; if (a[1] == a[2])//去重/2 k = 2; else k = 1; printf ("%lld\n", (x + y) / k); } }