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 来源
河南省第九届省赛
解题思路：
给定两个斜率，以这两条直线重新构造一个坐标轴，将符合条件的点存到一个结构体数组，将x从小到大排序，如果x相等将y从小到大排序。接下来就是最基础的LIS。注意如果LIS不用二分会超时。
代码如下：
#include <bits/stdc++.h> #define N 100005 using namespace std; struct node { double x,y; } no[N]; bool sort_cmp(node a,node b)//按照x坐标从小打到，如果x相等则按照y坐标从小到大 { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int Search(node b[],node num,int low,int high)//二分查找 { int mid; while(low<=high) { mid=(low+high)/2; if(num.y>b[mid].y) low=mid+1; else high=mid-1; } return low; } int lis(node a[],int n) { int k=1; node vis[N]; vis[0]=a[0]; for(int i=1; i<n; i++) { if(a[i].y>vis[k-1].y&&a[i].x>vis[k-1].x) { vis[k++]=a[i]; } else { int mid=Search(vis,a[i],0,k); vis[mid]=a[i]; } } return k; } int main() { int T; cin>>T; while(T--) { double k1,k2; int l[N]; int a,b,c,d,n,p=0; scanf("%d",&n); 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); for(int i=0; i<n; i++) { double ans; scanf("%d%d",&a,&b); ans=b*1.0/a; if(ans>k1&&ans<k2)//当其坐标符合要求，将其两条射线当做坐标轴处理 { no[p].x=a*1.0-b*1.0/k2; no[p].y=b*1.0-k1*a; l[p]=1; p++; } } sort(no,no+p,sort_cmp); cout<<lis(no,p)<<endl; } return 0; }
如果LIS不太了解可以点下面的
传送门
