【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
说点什么

1 Comment threads
0 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

Orz