#P4926. [1007] 倍杀测量者

    ID: 178 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Special Judge最短路差分约束差分洛谷月赛

[1007] 倍杀测量者

题目描述

今天 Scarlet 在机房有幸目睹了一场别开生面的 OI 训练。因为一些奇妙的 SPJ,比赛中所有选手的得分都是正实数(甚至没有上限)。

当一位选手 A 的分数不小于选手 B 的分数 kkk>0k>0)倍时,我们称选手 A kk 倍杀 了选手B,选手 B 选手 A kk 倍杀 了。

更奇妙也更激动人心的是,训练前有不少选手立下了诸如“我没 kk 倍杀选手 X,我就女装”,“选手 Y 把我 kk 倍杀,我就女装”的 Flag。

知道真相的良心教练 Patchouli 为了维持机房秩序,放宽了选手们的 Flag 限制。Patchouli 设定了一个 常数 TT,立下“我没 kk 倍杀选手 X 就女装”的选手只要成功 kTk-T 倍杀了选手 X,就不需要女装。同样的,立下“选手 Y 把我 kk 倍杀我就女装”的选手只要没有成功被选手 Y k+Tk+T 倍杀,也不需要女装。

提前知道了某些选手分数和具体 Flag 的 Scarlet 实在不忍心看到这么一次精彩比赛却没人女装,为了方便和 Patchouli 交易,Scarlet 想要确定最大的实数 TT 使得赛后一定有选手收 Flag 女装。

输入格式

第一行三个整数 n,s,tn,s,t,分别表示机房内选手人数,选手立下的 Flag 总数和 Scarlet 已知的选手分数的数量。nn 位选手从 11 开始编号至 nn,编号为 kk 的选手被称为选手 kk

接下来 ss 行,每行四个整数 o,A,B,ko,A,B,k。其中 o=1o=1 表示选手 A 立下了“我没 kk 倍杀选手 B 就女装”的Flag,o=2o=2 表示选手 A 立下了“选手 B 把我 kk 倍杀我就女装”的 Flag。

接下来 tt 行,每行两个整数 C,xC,x,表示 Scarlet 已知选手 CC 的分数为 xx

输出格式

若存在能保证赛后有选手女装的最大的 TT,则输出 TT,只有当输出与答案的绝对误差不超过 10410^{-4} 时才被视作正确输出。

若不存在,输出 -1

3 5 1
1 2 1 2
1 3 2 2
1 3 1 4
2 1 2 2
2 1 3 4
1 1
-1
3 2 3
1 2 1 10
2 2 3 6
1 1
2 6
3 9
3.9999993984

提示

对于 30%30\% 的数据,1n5,1s21\leq n\leq5,1\leq s\leq 2

对于另 40%40\% 的数据,保证 t=nt=n

对于 100%100\% 的数据,$1\leq n,s\leq 1000,1\leq A,B,C,t\leq n,1\leq k\leq 10,1\leq x\leq 10^9$。保证输入中的 CC 两两不同。