洛谷3222 [HNOI2012]射箭

Luogu

分析

除了卡精度都很简单的题。

显然二分答案,考虑如何 check。

设抛物线为 $y=ax^2+bx$,那么对于每个 $i$ 都应有

$$ y_{i_1}\leq ax_i\!^2+bx_i\leq y_{i_2}\\ $$

除掉一个 $x_i$ 可以得到

$$ \frac{y_{i_1}}{x_i}\leq ax_i+b\leq\frac{y_{i_2}}{x_i} $$

那么对于每个 $i$,$a,b$ 的解集都可以表示为两个半平面的交,因此我们只要把 $2\times mid$ 个半平面拿出来判断是否存在半平面交即可。

这题卡精度卡的我想死了 QAQ

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const double inf=1e11,eps=1e-11;

int n,m;
double x[N],l[N],r[N];

struct Point { double x,y; } p[N<<1];
typedef Point Vector;
struct Line { Point x; Vector y; double ang; } L[N<<1];
inline int cmp(Line a,Line b) { return a.ang<b.ang; }

Point operator +(Point a,Vector b) { return (Point){a.x+b.x,a.y+b.y}; }
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
Vector operator *(Vector a,double b) { return (Vector){a.x*b,a.y*b}; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
inline Point inter(Line a,Line b) {
    return a.x+a.y*(cross(b.y,b.x-a.x)/cross(b.y,a.y));
}
inline int inLeft(Point a,Line b) { return cross(b.y,a-b.x)>-eps; }
// 注意这里要写成 >-eps,因为本题中平行时是不需要去掉的,否则会 WA on #1。

inline int HalfPlane() {
    for (re int i=1;i<=m;++i) L[i].ang=atan2(L[i].y.y,L[i].y.x);
    sort(L+1,L+m+1,cmp); int h,t=1;
    for (re int i=2;i<=m;++i) {
        if (L[i].ang!=L[t].ang) L[++t]=L[i];
        else if (inLeft(L[i].x,L[t])) L[t]=L[i];
    }
    m=t,h=t=1;
    for (re int i=2;i<=m;++i) {
        while (h<t&&!inLeft(p[t],L[i])) --t;
        while (h<t&&!inLeft(p[h+1],L[i])) ++h;
        L[++t]=L[i];
        if (h<t) p[t]=inter(L[t-1],L[t]);
    }
    while (h<t&&!inLeft(p[t],L[h])) --t;
    p[h]=p[t+1]=inter(L[h],L[t]);
    return t-h>1;
}

inline int check(int mid) { m=0;
    for (re int i=1;i<=mid;++i) {
        L[++m]=(Line){(Point){0,l[i]/x[i]},(Vector){1,-x[i]},0};
        L[++m]=(Line){(Point){0,r[i]/x[i]},(Vector){-1,x[i]},0};
    }
    L[++m]=(Line){(Point){-inf,eps},(Vector){1,0},0};
    L[++m]=(Line){(Point){-eps,eps},(Vector){0,1},0};
    L[++m]=(Line){(Point){-eps,inf},(Vector){-1,0},0};
    L[++m]=(Line){(Point){-inf,inf},(Vector){0,-1},0};
    return HalfPlane();
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) x[i]=read(),l[i]=read(),r[i]=read();
    int L=1,R=n;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (check(mid)) L=mid;
        else R=mid-1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2019 年 11 月 02 日 03 : 06 PM

2 条评论

  1. smy

    怎么能咕呢

    1. M_sea
      @smy

      我真的不想咕,但是我求半平面交时把平行的直线给去掉了,然后无限 WA on #1 ...

发表评论