洛谷P3222 [HNOI2012]射箭

题目描述

沫沫最近在玩一个二维的射箭游戏，如下图 1 所示，这个游戏中的 x 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。

沫沫控制一个位于(0,0)的弓箭手，可以朝 0 至 90?中的任意角度（不包括 0度和 90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些只有端点被射中的靶子。

这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。

在闯关模式中，第一关只有一个靶子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出现一个靶子，在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关，否则游戏结束。

沫沫花了很多时间在这个游戏上，却最多只能玩到第七关”七星连珠“，这让她非常困惑。于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关

输入输出格式

输入格式：

输入文件第一行是一个正整数N，表示一共有N关。接下来有N行，第i+1行是用空格隔开的三个正整数xi，yi1，yi2(yi1<yi2 )，表示第i关出现的靶子的横坐标是xi，纵坐标的范围是从yi1到yi2 。输入保证30%的数据满足N<=100，50%的数据满足N<=5000，100%的数据满足N<=100000且给出的所有坐标不超过109 。

输出格式：

仅包含一个整数，表示最多的通关数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

数据已加强By WWT15。特鸣谢！---2015.03.09

直接考虑原问题不好考虑，我们先二分一下能过的关，考虑怎么验证。

容易发现虽然抛的是抛物线，但是经过原点。设轨迹解析式为y=ax(x-b)。发现每一个靶子对a,b的限制都是线性的，找出b关于a的关系式。然后我们只要查看这些限制的交集是否为空即可。

这题的坑在于不仅仅是靶子对抛物线有限制，还有生活实际的限制。首先抛物线必须开口朝下(a<0)，其次落点必须在y轴右侧(b>0)。

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 4e5 + 20;
const long double inf = 1e12;
const long double x0 = -20;
const long double x1 = 19;
int vis[maxn], n, cnt, x, h, l;

namespace G2D {
    typedef long double T;
    const T eps = 1e-18;
    int sgn(T x) {return (x > -eps) - (x < eps);}
    struct Point {
        T x, y; Point(){}
        Point(T rx, T ry) {x = rx, y = ry;}
        void prt() {
            //cerr << x << " " << y << endl;
            printf("%lf %lf\n", x, y);
        }
    };
    Point operator + (const Point &A, const Point &B) {
        return Point(A.x + B.x, A.y + B.y);
    }
    Point operator - (const Point &A, const Point &B) {
        return Point(A.x - B.x, A.y - B.y);
    }
    T operator * (const Point &A, const Point &B) {
        return (A.x * B.y - B.x * A.y);
    }
    Point operator * (const Point &A, const T &B) {
        return Point(A.x * B, A.y * B);
    }
    struct Line {
        T k; int id;
        Point s, t;Line() {}
        Line(Point rx, Point ry) 
            {s = rx, t = ry, id = 0;}
        void calc() {
            k = atan2((t - s).x, (t - s).y);
        }
        bool operator < (const Line &A) const {
            return sgn(A.k - k) > 0;
        }
    };
    Point cross(const Line &A, const Line &B) {
        T s1 = ((B.t - A.s) * (B.s - A.s)), s2 = ((B.s - A.t) * (B.t - A.t));
        return (A.t - A.s) * (s1 / (s1 + s2)) + A.s;
    }
    int AOnLeft(const Point &A, const Line &B) {
        return sgn((B.t - B.s) * (A - B.s));
    }
    int q[maxn], f, b;
    bool HPI(Line *l, int cnt, int x) {
        int tp = 0, tot = 0, lst = 0; f = 1, b = 0;
        while(tp < cnt) {
            ++tp;
            while(tp <= cnt && l[tp].id > x) 
                ++tp;
            if(tp == cnt + 1) break;
            //if(f < b) cross(l[q[b - 1]], l[q[b]]).prt();
            while(f < b && AOnLeft(cross(l[q[b - 1]], l[q[b]]), l[tp]) < 0)
                --b;
            //if(f < b) cross(l[q[f]], l[q[f + 1]]).prt();
            while(f < b && AOnLeft(cross(l[q[f]], l[q[f + 1]]), l[tp]) < 0)
                ++f;
            q[++b] = tp;
            //if (!sgn((l[q[b]].t - l[q[b]].s) * (l[q[b - 1]].t - l[q[b - 1]].s))) {
            //    --b;
            //}
        }
        while(f < b && AOnLeft(cross(l[q[b - 1]], l[q[b]]), l[q[f]]) < 0)
            --b;
        while(f < b && AOnLeft(cross(l[q[f]], l[q[f + 1]]), l[q[b]]) < 0)
            ++f;
        /*printf("#######\n");
        for(register int i = f; i < b; ++i)
            cross(l[i], l[i + 1]).prt();
        cross(l[b], l[f]).prt();*/
        if(b <= f + 1) return 0;
        return 1;
    }
}
using namespace G2D;
Line ls[maxn], nls[maxn];
int tp;

int solve(int l, int r) {
    while(l < r - 1) {
        int mid = l + r >> 1;
        if(G2D::HPI(nls, tp, mid)) l = mid;
        else r = mid;
    }
    return l;
}

int main() {
    //freopen("input8.in", "r", stdin);
    //freopen("log.txt", "w", stdout);
    scanf("%d", &n);
    /*for(register int i = 1; i <= n; ++i) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        ls[++cnt] = Line(Point(a, b), Point(c, d));
        ls[cnt].calc(), ls[cnt - 1].calc();
    }
    sort(ls + 1, ls + cnt + 1);
    printf("%d", HPI(ls));*/
    for(register int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &x, &l, &h);
        ls[++cnt] = Line(Point(x1, h * 1.0 / x - x1 * x),
                        Point(x0, h * 1.0 / x - x0 * x));
        ls[++cnt] = Line(Point(x0, l * 1.0 / x - x0 * x),
                        Point(x1, l * 1.0 / x - x1 * x));
        ls[cnt].id = ls[cnt - 1].id = i;
        ls[cnt].calc(), ls[cnt - 1].calc();
    }
    ls[++cnt] = Line(Point(-eps, inf), Point(-inf, inf));
    ls[cnt].calc();
    ls[++cnt] = Line(Point(-inf, inf), Point(-inf, eps));
    ls[cnt].calc();
    ls[++cnt] = Line(Point(-inf, eps), Point(-eps, eps));
    ls[cnt].calc();
    ls[++cnt] = Line(Point(-eps, eps), Point(-eps, inf));
    ls[cnt].calc();
    sort(ls + 1, ls + cnt + 1), nls[tp].k = 66662333;
    for(register int i = 1; i <= cnt; ++i) {
    	if(sgn(nls[tp].k - ls[i].k)) nls[++tp] = ls[i];
    	else if(AOnLeft(ls[i].s, nls[tp]) > 0)
    		nls[tp] = ls[i];
    }
    printf("%d", solve(1, n + 1));
    //cout << check(88888); 
    return 0;
}

Rockdu's Blog