题目链接:http://nyoj.top/problem/1275

  • 内存限制:64MB 时间限制:1000ms

题目描述

Alpha 机构研发出一种新型智能导弹，它能够在雷达检测到的区域内，选择一条前进的路径， 击破路径上所有的目标物。 雷达位于（0,0）处，它能够检测到两条射线之间的区域（不妨设在第一象限）。 导弹一开始置放在（0,0）处，它可以在雷达能检测到的区域内先选择一个目标物击破，然后 再继续前进，选择另一个目标物击破。注意，导弹不能沿着这两条射线前进，当然也不能停在原 地。 可以假设，导弹一旦发射，其能量无比大，前进的路径无限长。 已知雷达能够检测到区域，其射线 1：ax-by=0 和射线 2：cx-dy=0。Alpha 机构的总指挥希望 在发现目标群的第一时刻，计算出一条可以击破最多目标物的路径。 

输入描述

第一行： T 表示以下有 T 组测试数据（1≤T ≤8）
对每组测试数据：
第 1 行： n 表示目标物的个数
第 2 行： a b c d 代表两条射线的斜率分别是 a/b 和 c/d。
接下来有 n 行，每行 2 个正整数 xi yi 即第 i 个目标物的坐标。
【约束条件】
 (1) n<=10^5 0<=a, b, c, d<=10^5 a 和 b 不会同时为 0，c 和 d 不会同时为 0;
(2) 0<= xi , yi <=10^6 i=1,…..,n

输出描述

每组测试数据，输出占一行，即导弹能击破的最多目标数。

样例输入

1
15
1 3 2 1
3 1
6 2
4 2
2 5
4 5
6 6
3 4
1 6
2 1
7 4
9 3
5 3
1 3
15 5
12 4

样例输出

4

解题思路

寻找射线内不与两条射线平行的LIS，首先输入的时候计算斜率，判断每个点是否在射线内，然后就是重建坐标系，方便判断递增，我采用的方法是，将横坐标减去该点在上射线投影点的x值，纵坐标减去该点在下射线投影点的y值，将坐标转换完毕后就是平面上的LIS问题了，不过要注意的是只能使用二分的方法写，不然会超时。 

#include <bits/stdc++.h>
using namespace std;
struct edge {
    double x, y;
}e[100005], dp[100005];
bool cmp(edge A, edge B) {
    if (A.x != B.x)
        return A.x < B.x;
    return A.y > B.y;
}
int Search(int k, int l, int r) {
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (dp[mid].y < e[k].y)
            l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
int main() {
    int t, l, k, n;
    double a, b, c, d, x, y, k1, k2, k3;
    scanf("%d", &t);
    while (t--) {
        k = l = 0;
        scanf("%d", &n);
        scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
        k2 = a / b;
        k1 = c / d;
        if (k1 < k2)
            swap(k1, k2);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &x, &y);
            k3 = y / x;
            if (k3 > k2 && k3 < k1) {
                e[k].x = x - y / k1;
                e[k++].y = y - k2 * x;
            }
        }
        sort(e, e + k, cmp);
        dp[l++] = e[0];
        for (int i = 1; i < k; i++) {
            if (e[i].x > dp[l - 1].x && e[i].y > dp[l - 1].y)
                dp[l++] = e[i];
            else {
                int mit = Search(i, 0, l);
                dp[mit] = e[i];
            }
        }
        printf("%d\n", l);
    }
    return 0;
}