【BZOJ2732】【HNOI2012】射箭

。。我弱到家了。。我决定重新把这个题做一遍

首先假设箭的方程为\(ax^2+bx=0(a<0)\)

我们想让箭通过第\(i\)个靶子,就要满足\(ax_i^2+bx_i\in[y1,y2]\)

拆开得到两个对\(a,b\)的限制条件\(ax^2+bx-y1\ge 0,ax^2+bx-y2\le 0\)

可以发现是两个半平面。

那么如果要通过前\(i\)关就需要前\(i\)关的半平面交集不为空。

于是二分答案,求半平面交。

由于最后的半平面交可能无限大,所以需要添加一个边框。注意网上大多数的代码都是错的因为没有考虑\(a<0\)的条件。边框只要左半部分就可以了。

 

BTW,这道题百度第一版的代码全被我拍WA了

 

说点什么

1 评论 在 "【BZOJ2732】【HNOI2012】射箭"

提醒
排序:   最新 | 最旧 | 得票最多
成员

Orz

wpDiscuz