#P3819. Breaking Bomber

    ID: 3021 传统题 4000ms 256MiB 尝试: 6 已通过: 2 难度: 10 上传者: 标签>CF3500NOI/NOI+/CTS坐标变换三维凸包随机增量算法扫描线离线查询有序集合行列式有理数精确运算区间算术Andrew 算法凸多边形二分查询凸多面体极对偶2015年国家集训队测试

Breaking Bomber

题目描述

有 nn 种原药,每种可以取任意非负实数份。第 ii 种原药的一份由四种成分组成,含量向量为 vi=(ai,bi,ci,di)v_i=(a_i,b_i,c_i,d_i)。可混合任意多种原药。取 wiw_i 份第 ii 种原药后,混合物的向量为 v=∑i=1nwiviv=\sum_{i=1}^n w_i v_i,其中 wi≥0w_i\ge0,并且至少有一种原药取了正数份。

有两类询问。第一类询问能否配出四种成分的含量恰好为 (A,B,C,D)(A,B,C,D) 的药剂。第二类询问能否配出一份非空药剂,使 Av1+Bv2+Cv3+Dv4≥0A v_1+B v_2+C v_3+D v_4\ge0,其中 v1,v2,v3,v4v_1,v_2,v_3,v_4 是混合物的四种成分含量。

输入格式

第一行一个整数 nn。接下来 nn 行,每行四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i。

再一行一个整数 mm。接下来 mm 行,每行五个整数 q,A,B,C,Dq,A,B,C,D。q=1q=1 或 22,分别对应两类询问。

输出格式

对每个询问输出一行。可以配出符合要求的药剂时输出 Y,否则输出 N。

样例

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 1 2 3 4
1 2 1 3 4
2 1 1 1 1
2 -1 -1 -1 -1
Y
Y
Y
N

数据范围与约定

4≤n≤500004\le n\le 50000,1≤m≤1000001\le m\le100000。所有输入的成分和环境参数的绝对值均小于 10910^9。

本站数据中,原药的四种成分均非负,且总含量为正。第一类询问的四种目标含量均非负,且总含量为正。第二类询问给出的是环境参数,可以为负。

清华集训原题 · 原赛讲解中的数学模型