一刀二分三角【牛客tracker & 每日一题】-171主机测评

一刀二分三角

时间限制：1 秒空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

二维直角坐标系中有一个三角形

ABC

$A B C$ ，其三个顶点坐标为

(

)

A(0, 0)

$A (0, 0)$ 、

(

)

B(x_b, 0)

$B (x_{b}, 0)$ 、

(

)

C(x_c, y_c)

$C (x_{c}, y_{c})$ ，其中保证

0 < x_c < x_b

$0 < x_{c} < x_{b}$ ，

y_c > 0

$y_{c} > 0$ 。

判断是否存在一个非负整数

≤

0 \\le x_0 \\le x_b

$0 \leq x_{0} \leq x_{b}$ ，使得沿

x = x_0

$x = x_{0}$ 将三角形切开后，得到的两个平面图形面积相同。

输入描述

输入第一行是一个整数

(

≤

)

T\\ (1 \\le T \\le 10^4)

$T (1 \leq T \leq 1 0^{4})$ ，样例组数。

每组样例包括三个空格分隔的正整数

(

≤

)

x_b, x_c, y_c\\ (0 < x_b, x_c, y_c \\le 10^3)

$x_{b}, x_{c}, y_{c} (0 < x_{b}, x_{c}, y_{c} \leq 1 0^{3})$ ，还保证

0 < x_c < x_b

$0 < x_{c} < x_{b}$ 。

输出描述

对每组样例，输出 “YES” 或 “NO”（全大写，不含引号）表示是否可以得到两个面积相同的平面图形。

示例 1

输入：

3
4 2 4
27 3 15
25 13 22

输出：

YES
YES
NO

数据范围

$\\le T \\le 10^4 1≤T≤104$
$x_b, x_c, y_c \\le 10^3 0<xb,xc,yc≤103$
$x_c < x_b 0<xc<xb$

解题思路

本题是面积平分 + 整数解判定的数学问题。三角形顶点为

(

)

A(0,0)

$A (0, 0)$ 、

(

)

B(x_b,0)

$B (x_{b}, 0)$ 、

(

)

C(x_c,y_c)

$C (x_{c}, y_{c})$ ，且满足

0<x_c<x_b,\\ y_c>0

$0 < x_{c} < x_{b}, y_{c} > 0$ 。要求判断是否存在非负整数

∈

[

]

x_0\\in[0,x_b]

$x_{0} \in [0, x_{b}]$ ，使得沿竖直直线

x=x_0

$x = x_{0}$ 将三角形切开后，左右两部分面积相等。

1. 问题等价转化

直线

x=x_0

$x = x_{0}$ 将三角形分成左右两部分。由于三角形在

x=x_c

$x = x_{c}$ 处存在“拐点”，左侧面积函数需要分段表示：

当

0

≤

x

0

≤

x

c

0\\le x_0\\le x_c

$0 \leq x_{0} \leq x_{c}$ 时，左侧是一个与

△

A

B

C

\\triangle ABC

$△ A B C$ 相似的小三角形，其面积为

S

左

=

y

c

2

x

c

x

0

2

S_{\\text{左}}=\\frac{y_c}{2x_c}x_0^2

$S_{左} = \frac{y _{c}}{2 x _{c}} x_{0}^{2}$
当

x

c

≤

x

0

≤

x

b

x_c\\le x_0\\le x_b

$x_{c} \leq x_{0} \leq x_{b}$ 时，左侧面积等于总面积减去右侧小三角形面积，即

S

左

=

S

总

−

y

c

2

(

x

b

−

x

c

)

(

x

b

−

x

0

)

2

S_{\\text{左}}=S_{\\text{总}}-\\frac{y_c}{2(x_b-x_c)}(x_b-x_0)^2

$S_{左} = S_{总} - \frac{y _{c}}{2 ( x _{b} - x _{c} )} (x_{b} - x_{0})^{2}$ 其中总面积

S

总

=

x

b

y

c

2

S_{\\text{总}}=\\frac{x_b y_c}{2}

$S_{总} = \frac{x _{b} y _{c}}{2}$

于是面积平分条件

左

总

S_{\\text{左}}=\\frac{S_{\\text{总}}}{2}

$S_{左} = \frac{S _{总}}{2}$ 可分别在两段上转化为关于

x_0

$x_{0}$ 的二次方程。

2. 核心推导

第一段

0

≤

x

0

≤

x

c

0\\le x_0\\le x_c

$0 \leq x_{0} \leq x_{c}$ ：

y

c

2

x

c

x

0

2

=

x

b

y

c

4

⟹

2

x

0

2

=

x

b

x

c

\\frac{y_c}{2x_c}x_0^2=\\frac{x_b y_c}{4} \\quad\\Longrightarrow\\quad 2x_0^2=x_b x_c

$\frac{y _{c}}{2 x _{c}} x_{0}^{2} = \frac{x _{b} y _{c}}{4} ⟹ 2 x_{0}^{2} = x_{b} x_{c}$ 因此需要

x

b

x

c

x_b x_c

$x_{b} x_{c}$ 为偶数，且

x

b

x

c

2

\\frac{x_b x_c}{2}

$\frac{x _{b} x _{c}}{2}$ 为完全平方数。记

x

0

=

x

b

x

c

2

x_0=\\sqrt{\\frac{x_b x_c}{2}}

$x_{0} = \frac{x _{b} x _{c}}{2}$

还需验证

0

≤

x

0

≤

x

c

0\\le x_0\\le x_c

$0 \leq x_{0} \leq x_{c}$ 。
第二段

x

c

≤

x

0

≤

x

b

x_c\\le x_0\\le x_b

$x_{c} \leq x_{0} \leq x_{b}$ ：令

u

=

x

b

−

x

0

u=x_b-x_0

$u = x_{b} - x_{0}$ ，则

y

c

2

(

x

b

−

x

c

)

u

2

=

x

b

y

c

4

⟹

2

u

2

=

x

b

(

x

b

−

x

c

)

\\frac{y_c}{2(x_b-x_c)}u^2=\\frac{x_b y_c}{4} \\quad\\Longrightarrow\\quad 2u^2=x_b(x_b-x_c)

$\frac{y _{c}}{2 ( x _{b} - x _{c} )} u^{2} = \frac{x _{b} y _{c}}{4} ⟹ 2 u^{2} = x_{b} (x_{b} - x_{c})$ 因此需要

x

b

(

x

b

−

x

c

)

x_b(x_b-x_c)

$x_{b} (x_{b} - x_{c})$ 为偶数，且

x

b

(

x

b

−

x

c

)

2

\\frac{x_b(x_b-x_c)}{2}

$\frac{x _{b} ( x _{b} - x _{c} )}{2}$ 为完全平方数。记

u

=

x

b

(

x

b

−

x

c

)

2

,

x

0

=

x

b

−

u

u=\\sqrt{\\frac{x_b(x_b-x_c)}{2}},\\qquad x_0=x_b-u

$u = \frac{x _{b} ( x _{b} - x _{c} )}{2}$

,x0=xb−u 还需验证

x

c

≤

x

0

≤

x

b

x_c\\le x_0\\le x_b

$x_{c} \leq x_{0} \leq x_{b}$ 。

注意：

y_c

$y_{c}$ 在面积等式中会被约去，因此它只影响坐标，不影响整数解是否存在。

3. 边界与判定细节

对于每组数据，依次检查两种可能：

令

s

=

x

b

x

c

s=x_b x_c

$s = x_{b} x_{c}$ 。若

s

s

$s$ 为偶数，令

t

=

s

/

2

t=s/2

$t = s /2$ 。判断

t

t

$t$ 是否为完全平方数；若是，令

x

0

=

t

x_0=\\sqrt t

$x_{0} = t$

，并检查

x

0

≤

x

c

x_0\\le x_c

$x_{0} \leq x_{c}$ 。
令

s

=

x

b

(

x

b

−

x

c

)

s=x_b(x_b-x_c)

$s = x_{b} (x_{b} - x_{c})$ 。若

s

s

$s$ 为偶数，令

t

=

s

/

2

t=s/2

$t = s /2$ 。判断

t

t

$t$ 是否为完全平方数；若是，令

u

=

t

u=\\sqrt t

$u = t$

，则

x

0

=

x

b

−

u

x_0=x_b-u

$x_{0} = x_{b} - u$ ，并检查

x

0

≥

x

c

x_0\\ge x_c

$x_{0} \geq x_{c}$ ，即

u

≤

x

b

−

x

c

u\\le x_b-x_c

$u \leq x_{b} - x_{c}$ 。

只要上述任一情况成立，则存在合法的整数

x_0

$x_{0}$ ，输出 YES；否则输出 NO。

4. 算法实现

每组读入 $x_b,x_c,y_c xb,xc,yc。$
分别计算 $x_b x_c xbxc 与 x b ( x b − x c ) x_b(x_b-x_c) xb(xb−xc)。$
若对应值为偶数，则取一半后判断是否为完全平方数。
对求得的候选 $x_0 x0 检查其是否落在对应的整数区间内。$
任一分支满足条件即输出 YES，否则输出 NO。

5. 复杂度分析

时间复杂度：每组数据只需常数次整数乘法、除法、开平方判断和区间比较，复杂度为 $T\\le 10^4 T≤104 组，总运算量极小。$
空间复杂度：仅使用常数个变量，空间复杂度为

总结

通过按

x_c

$x_{c}$ 将三角形面积函数分段，把面积平分问题转化为两个二次方程。再将整数解存在性转化为“某个数的一半是否为完全平方数”以及候选解是否落在对应区间内。整个判定过程只涉及整数运算，避免了浮点误差，逻辑清晰且实现简单。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

bool solve()
{
ll a,b,c;
cin>>a>>b>>c;
ll s=a*b;
if(s%2==0)
{
ll x=sqrt(s/2);
if(x<=b&&2*x*x==s)return true;
}
s=a*(a–b);
if(s%2==0)
{
ll x=a–sqrt(s/2);
if(x>=b&&2*(x–a)*(x–a)==s)return true;
}
return false;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T—) cout<<(solve()?"YES":"NO")<<"\\n";
return 0;
}

一刀二分三角【牛客tracker & 每日一题】