本文主要是介绍COGS 2085 Asm.Def的一秒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
“你们搞的这个导弹啊，excited！”
Asm.Def通过数据链发送了算出的疑似目标位置，几分钟后，成群结队的巡航导弹从“无蛤”号头顶掠过，布满了天空。
“一共发射了多少导弹？”
“十亿美元。”斯科特·华莱士回答，“单价100万，现在天上有1000多枚。这玩意能自动搜索10个可疑点，找到目标就发动攻击。”
“什么？10个？我给了它10万个点！”
“这会让它的程序崩溃的。好在你还有时间手动输入路径。”
“多久？”
“零……还有一秒，他们又给续上了一秒。”
“我想静静，别问我静静是谁。”
Asm.Def在第一象限内找到了n个可疑点。他需要为导弹规划路径。
如图所示，导弹一开始在(0,0)。它只能朝着一定的方向——即严格夹在图中两条射线间的方向（白色部分）前进。注意，它不能沿着这两条射线前进，当然也不能停在原地。
当导弹到达某个可疑点后，它仍然只能朝着该范围内的方向前进，如图。
Asm.Def想要让导弹经过尽可能多的可疑点。他需要在一秒钟内知道，最多能经过多少个可疑点。
【输入格式】
第1行1个整数n。
第2行4个整数a b c d：代表两条射线的斜率分别是a/b和c/d。保证0<=a,b,c,d<=10^5，a/b<c/d（即a/b是靠下的那条射线），a/b≠0/0，c/d≠0/0.
接下来n行，每行2个整数xi,yi（1<=xi,yi<=10^5），代表i号可疑点的坐标。
【输出格式】
一行一个整数，即最多能经过几个可疑点。
【样例输入】
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
【提示】
这是最佳路径。注意，导弹不能前往位于射线上的点。
对于30%的数据，n<=1000，a=0,b=1,c=1,d=0。
对于60%的数据，n<=1000。
对于100%的数据，n<=10^5。
看到这题目背景，窝只想说excited！
来看一个简单一点的问题：如果两条边界线是x轴，y轴呢？
是不是很简答？
将点的坐标按x排序，再对y求lis。
那剩下的问题就是求每个点在新坐标系的坐标。
这个叉积一下就好了嘛，不需要求具体点坐标，只需要知道它是单位向量的多少倍就好了。
又因为除数显然相同，可以考虑不用double。
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m;
long long q[N];
struct node
{long long x,y;
}t1,t2,v[N];
long long cross(node a,node b)
{return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b)
{if(a.x==b.x)return a.y<b.y;return a.x<b.x;
}
int main()
{freopen("asm_second.in","r",stdin);freopen("asm_second.out","w",stdout);scanf("%d%lld%lld%lld%lld",&n,&t1.y,&t1.x,&t2.y,&t2.x);for(int i=1;i<=n;i++){node t;scanf("%lld%lld",&t.x,&t.y);v[i].y=cross(t1,t);v[i].x=cross(t,t2);}sort(v+1,v+n+1,cmp);for(int i=1;i<=n;i++)if(v[i].x>0&&v[i].y>0){if(v[i].y>q[m])q[++m]=v[i].y;elseq[lower_bound(q+1,q+m+1,v[i].y)-q]=v[i].y;}printf("%d\n",m);return 0;
}这篇关于COGS 2085 Asm.Def的一秒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
