XVII.[HNOI2012]射箭
强烈谴责本道卡精度屑题。
首先，乍一看，二次函数\(ax^2+b\)在\(x=x_0\)处的值要在\([y_0,y_1]\)之内？带进去不就是一个关于\(a,b\)的半平面交吗？
然后再一看，要找到半平面交非空的最大位置， 难不成要用动态凸包？
后来想想动态凸包什么的完全没有必要啦，直接二分一下即可。
同时，满足题意的凸包，必须有 \(a<0,b>0\)，于是我们加入四条边界线即可。
然后就开始疯狂debug了。
下面扯一些我犯的蠢蠢的错误：
- 将向量和直线模板化过度，以至于某些本来没有意义的符号也变的有意义了。
例：我定义了向量和向量间的&符号、直线和直线间的&符号、向量和直线间的&符号，然后就开始混用三个符号了……
- 滥用
atan2函数。
atan2函数还是有一定的常数的，滥用会使得程序常数过大。
- 使用了\(O(n\log^2n)\)的算法。
应该在最外面就先把所有直线排好序，这样单次半平面交就是\(O(n)\)的了。
同时，还需要一点点耐心，一点点long double和一点点1e-15的精度……
代码：
#include<bits/stdc++.h>
using namespace std;
#define double long double
const double eps=1e-15;
const double inf=1e11;
int cmp(double x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
struct Vector{
double x,y;
Vector(){}
Vector(double X,double Y){x=X,y=Y;}
friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
double operator !()const{return atan2(y,x);}//the angle of a vector
};
typedef Vector Point;
struct Line{
Point x;
Vector z;
double ag;
Line(){}
Line(Point X,Point Y){x=X,z=Y-X,ag=!z;}
friend bool operator <(const Line &u,const Line &v){return u.ag<v.ag;}
friend bool operator ^(const Line &u,const Point &v){return cmp(u.z&(v-u.x))==-1;}
friend Point operator &(const Line &u,const Line &v){
return u.x+u.z*((v.z&(u.x-v.x))/(u.z&v.z));
}
}l[200100],a[200100];
Point p[200100];
int L,R,ord[200100],n,m;
typedef Line Segment;
bool Semiplane_Intersection(int lim){
int i=1;
while(ord[i]>lim)i++;
l[L=R=1]=a[ord[i]];
for(i++;i<=m;i++){
if(ord[i]>lim)continue;
while(L<R&&a[ord[i]]^p[R-1])R--;
while(L<R&&a[ord[i]]^p[L])L++;
if(a[ord[i]].ag!=l[R].ag)l[++R]=a[ord[i]];
else if(a[ord[i]]^l[R].x)l[R]=a[ord[i]];
if(L<R)p[R-1]=l[R]&l[R-1];
}
while(L<R&&l[L]^p[R-1])R--;
return R-L>1;
}
int read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int main(){
n=read();
a[1]=Line(Point(-inf,eps),Point(-eps,eps));
a[2]=Line(Point(-eps,eps),Point(-eps,inf));
a[3]=Line(Point(-eps,inf),Point(-inf,inf));
a[4]=Line(Point(-inf,inf),Point(-inf,eps));
for(int i=1;i<=n;i++){
double x=read(),y=read(),z=read();
a[2*i+3]=Line(Point(0,y/x),Point(1,y/x-x));
a[2*i+4]=Line(Point(1,z/x-x),Point(0,z/x));
}
m=2*n+4;
for(int i=1;i<=m;i++)ord[i]=i;
sort(ord+1,ord+m+1,[](int u,int v){return a[u]<a[v];});
// for(int i=1;i<=2*n+4;i++)a[i].x.print(),a[i].y.print(),puts("");
int l=0,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(Semiplane_Intersection(2*mid+4))l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}