#P10499. [2021年联测]极限火花

    ID: 9616 传统题 4000ms 512MiB 尝试: 6 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-暴力枚举区间求交区间合并有理数精确运算

[2021年联测]极限火花

题目描述

玩家可在二维平面的矩形 0≤x≤X, 0≤y≤Y0\le x\le X,\ 0\le y\le Y 内移动,包含边界。游戏中有 nn 个覆盖区域。每个区域由四个整数 A,B,C,DA,B,C,D 描述,覆盖所有满足 C≤Ax+By≤DC\le Ax+By\le D 的点,包含两条边界线。

若矩形内至少存在一个点没有被任何区域覆盖,则存在安定点。坐标可以是任意实数。对每组数据判断是否存在安定点。

输入格式

第一行一个整数 TT,表示数据组数。每组数据先输入三个整数 X,Y,nX,Y,n,接下来 nn 行,每行四个整数 A,B,C,DA,B,C,D。

输出格式

输出一个长度为 TT 的二进制串,第 ii 个字符表示第 ii 组数据是否存在安定点。存在输出 1,否则输出 0。字符之间没有空格或换行。

样例

2
1 1 2
1 -1 -1 0
2 -1 0 2
1 1 2
1 -1 -1 0
1 -2 0 1
01

第一组两个区域覆盖了整个矩形。第二组中,点 (3/4,1/2)(3/4,1/2) 不在任何区域内。

数据范围

1≤X,Y≤10001\le X,Y\le1000,1≤n≤20001\le n\le2000,所有数据组的 nn 之和不超过 20002000。每个覆盖区域满足 ∣A∣,∣B∣,∣C∣,∣D∣≤1000|A|,|B|,|C|,|D|\le1000,A2+B2>0A^2+B^2>0,C≤DC\le D。

原子任务 分值 附加限制
1 15 n=1n=1
2 10 n≤2n\le2
3 15 所有 A=0A=0
4 所有 A,BA,B 均非零
5 n≤500n\le500
6 30 无

原 PDF 题面及样例示意图