题目描述
恋符「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。
样例输入
样例输出