PID715 / 超极限火花
题目描述

恋符「Master Spark」是巫女雾雨魔理沙的招牌技能。其破坏力巨大。

这里,我们把世界想象成一个矩形。其左下角坐标是(0, 0),右上角是(W, H)。

同时,为了简化问题,我们把弹幕作如下化简。

原弹幕可以视作一个以(x0, y0)为顶点的等腰三角形,其顶角为α度,而弹幕一直延伸到直线Y=H。所以我们可以用三元组(xi0, yi0, αi)来描述一个弹幕。

值得注意的是,弹幕不会超出世界的范围,所以有时候弹幕不是一个严格的等腰三角形。

现在有N个可以释放Master Spark,魔理沙想知道,最少用几个弹幕,就可以完全控制版底(即直线Y=H)。这里的“控制“指的是:在直线Y=H上的任意一个点,都至少被一个弹幕攻击到。

【Hint】

选择第1个和第3个弹幕。

对于30%:N<=15

对于60%:N<=1000

对于100%:N<=100000 0 < W, H <= 1000000

输入格式

第一行三个整数,W, H, N

接下来N行,每行3个整数x0, y0, αi,保证(x0, y0)在矩形范围内,αi以角度的形式输入,数值在区间(0, 180)内

输出格式

一个整数,表示最小的弹幕数。

如果不存在一种方案能控制整个版底,输出-1。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论