33OJ
登录 注册

#P17518. [ECUSTPC 2026 Fall] 凸包

    ID: 20246 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度普及 上传者: 标签>数学Special Judge2026高校校赛

[ECUSTPC 2026 Fall] 凸包

背景

我知道既不是凸包也不是凹包的我为什么要哭的。因为我其实是一只豆包。

题目描述

给定 nn 个一元二次不等式,每个不等式的形式为:

aix2+bix+ci>0a_i x^2 + b_i x + c_i > 0

对任意 1≤i≤n1 \le i \le n ,保证 ai<0a_i < 0 。

请你判断是否存在整数 xx,使得这 nn 个不等式同时成立。

输入格式

第一行输入一个整数 TT (1≤T≤1041 \le T \le 10^4),表示测试数据的数量。

每组测试数据第一行输入一个整数 nn (1≤n≤2×1051 \le n \le 2 \times 10^5),表示不等式的个数。

随后 nn 行,每行输入三个整数 ai,bi,cia_i, b_i, c_i (−105≤ai≤−1-10^5 \le a_i \le -1, −105≤bi,ci≤105-10^5 \le b_i, c_i \le 10^5),表示第 ii 个不等式的三个系数。

保证所有测试数据的 ∑n≤2×105\sum n \le 2 \times 10^5。

输出格式

对于每组测试数据,若存在整数 xx 同时满足所有不等式,输出一行 YES,否则输出一行 NO。

注意评测时不会区分 YES 和 NO 的大小写。换言之,当答案是肯定的时候输出 yes、YES、Yes、YeS 等都会被认为是正确的。

5
2
-1 0 4
-1 4 -3
3
-1 100000 0
-1 202 10000
-2 400 19998
2
-1 2 0
-1 0 -1
2
-100000 0 100000
-1 0 4
2
-1 2 0
-1 4 -3

NO
YES
NO
YES
NO

提示

样例 1 解释

对于第 44 组测试数据,当 x=0x=0 时,两个不等式均成立,因此存在整数解。