导弹发射

时间限制： 1000 ms  |  内存限制： 65535 KB
难度： 4
<dl class="problem&#45;display" style="font&#45;size&#58;14px&#59;color&#58;rgb&#40;70&#44;70&#44;70&#41;&#59;font&#45;family&#58;Tahoma&#44; Arial&#44; sans&#45;serif&#44; simsun&#59;"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 描述 </dt> <dd style="margin&#45;left&#58;0px&#59;">

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

</dd> </dl>
<dl class="others"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 输入 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 第一行： 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 </dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 输出 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 每组测试数据，输出占一行，即导弹能击破的最多目标数。
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 样例输入 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 
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
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 样例输出 </dt> <dd style="margin&#45;left&#58;0px&#59;">

4

</dd> <dd style="margin&#45;left&#58;0px&#59;"> 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
    double x,y;
}node[100005];
Node ans[10005];
int len;
bool cmp(Node a,Node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
int binary_search(int i)
{
    int left=0,right=len;
    int mid;
    while(left<=right){
        mid=(left+right)/2;
        if(ans[mid].y<node[i].y) left=mid+1;
        else right=mid-1;
    }
    return left;
}
int main()
{
    int T,k;
    scanf("%d",&T);
    while(T--)
    {
        k=0;
        int n;
        cin>>n;
        int a,b,c,d;
        double k1,k2,k3,t;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        k1=a*1.0/b;
        k2=c*1.0/d;
        if(k1>k2)
            swap(k1,k2);
        int x,y;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            k3=1.0*y/x;
            if(k3>k1&&k3<k2){
                node[k].x=x*1.0-y*1.0/k2;
                node[k].y=y*1.0-k1*x;
                k++;
            }
        }
        sort(node,node+k,cmp);
        memset(ans,0,sizeof(ans));
        len=1;
        ans[0]=node[0];
        for(int i=1;i<n;i++){
            if(node[i].y>ans[len-1].y&&node[i].x>ans[len-1].x){
                ans[len++]=node[i];
            }
            else{
                int pos=binary_search(i);
                ans[pos]=node[i];
            }
        }
        printf("%d\n",len);
    }
    return 0;
}
</dd> </dl>

以两条射线重建坐标系，在坐标系里面跑最长递增子序列