【bzoj2732】[HNOI2012]射箭

Description

Input

Output

Sample Input

Sample Output

HINT

Source



非常坑的题目。。。

这题的主要思路就是半平面交+二分

我们先二分一个能通过的关卡数

然后对于一个关卡来说，如果一个抛物线能通过它，显然有

y1 <= ax ^ 2 + bx <= y2

由于两个不等式是相似的，我们这里只考虑第一个

ax ^ 2 + bx >= y1

变换一下 

bx >= y1 - ax ^ 2

b >= y1 / x - ax

这时候我们可以把-ax + y1 / x看成一条直线，于是就变成了线性规划的样子

跑一遍半平面交，判一下当前条件下是否有解，即半平面是否不为空即可

但是！但是

这题的坑点还没有展现出来。。

如果你交了这题，你会惊奇地发现

这题tm卡精度！！！！！

呵呵我还能说什么

这题不能用double，必须要开long double..........

eps要反复尝试。。。。一般开到1e-20

然后，就算是这样。。。lz的代码依然WA了？？？？

要到数据以后本地测AC？？？？？？？

还能有这种操作？？？？？？？

代码（本地测AC，bzoj上WA的代码，谨慎提交）：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;typedef long double DL;const DL s = 200201;
const DL eps = 1e-20;
const int maxn = 100100;struct point{DL x,y;
}p[2 * maxn];struct vec{point p;DL x,y,pri;int id;
}L[2 * maxn],a[2 * maxn],q[2 * maxn];int n,m,tot,head,tail,l,r,ans;inline vec link(point a,point b)
{return (vec){b, a.x - b.x, a.y - b.y,0,0};
}inline DL cross(vec a,vec b)
{return a.x * b.y - a.y * b.x;
}inline bool larger(DL a,DL b)
{return a - b > eps;
}inline bool equal(DL a,DL b)
{return fabs(a - b) <= eps;
}inline bool smaller(DL a,DL b)
{return larger(b,a);
}inline bool onleft(vec a,point b)
{vec tmp = link(b,a.p);return larger(cross(a,tmp),0) || equal(cross(a,tmp),0);
}inline point intersection(vec a,vec b)
{vec tmp = link(a.p,b.p);DL t = cross(b,tmp) / cross(a,b);return (point){a.p.x + t * a.x,a.p.y + t * a.y};
}inline bool judge(int k)
{tot = 0;for (int i = 1; i <= m; i++) if (L[i].id <= k) a[++tot] = L[i];q[head = tail = 1] = a[1];for (int i = 2; i <= tot; i++){while (head < tail && !onleft(a[i],p[tail - 1])) tail--;while (head < tail && !onleft(a[i],p[head])) head++;q[++tail] = a[i];if (equal(q[tail].pri,q[tail - 1].pri)){tail--;if (onleft(q[tail],a[i].p)) q[tail] = a[i];}if (head < tail) p[tail - 1] = intersection(q[tail],q[tail - 1]);}while (head < tail && !onleft(q[head],p[tail - 1])) tail--;return tail - head > 1;
}inline bool cmp(vec a,vec b)
{return smaller(a.pri,b.pri);
}inline int getint()
{int ret = 0;char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9')ret = ret * 10 + c - '0',c = getchar();return ret;
}int main()
{n = getint();for (int i = 1; i <= n; i++){DL x = getint(),y1 = getint(),y2 = getint();DL k = -x,b = y1 / x;point p1 = (point){0,b},p2 = (point){1,k + b};L[++m] = link(p2,p1); L[m].pri = atan2(L[m].y,L[m].x); L[m].id = i;k = -x; b = y2 / x;p1 = (point){0,b},p2 = (point){1,k + b};L[++m] = link(p1,p2); L[m].pri = atan2(L[m].y,L[m].x); L[m].id = i;}sort(L + 1,L + m + 1,cmp);l = 1; r = n;while (r - l > 1){int mid = l + r >> 1;if (judge(mid)) l = mid;else r = mid;}if (judge(r)) ans = r;else ans = l;printf("%d",ans);return 0;
}