题目描述
ZMiG成功粉碎了707的基因突变计划,为了人类的安全,他决定向707的科学实验室发起进攻!707并没有想到有人敢攻击她的实验室,一时间不知所措,决定牺牲电力来换取自己实验室的平安。
在实验室周围瞬间产生了一个无限大的力场护盾,它看上去无懈可击!不过ZMiG拥有惊人的双向观察能力,经过他的反复观察,找到了这个护盾的N个弱点,他本想逐一击破,却发现一股神秘力量阻止了他的行为。原来他身处力场之中,受到了两股神秘力量的影响,这两股力量来自两个不同的方向并形成了一个小于180度的角,ZMiG每次可攻击的范围都受到这两个力的影响,当他攻击了点X之后,下一次可以攻击的点必须在以X为坐标原点的情况下,这两个力方向的夹角之间(包含边界)(具体意思可看样例) ZMiG当然想打出一串最长的Combo,所以他想问问你最多可以攻击707弱点多少次数据范围
对于所有数据,-10^9<=X,Y,X1,Y1,X2,Y2<=10^9
对于 30%的数据, n<=1000 对于另外20%的数据,保证X1=1,Y1=0,X2=0,Y2=1 对于 100%的数据,n<=200000解法
把每一个点看作是向量。
以题目给定的两个向量建立坐标系。 对于第i个向量,考虑将它的坐标转移到这个坐标系上,用(x1,y1)的系数表示它的横坐标,(x2,y2)的系数表示它的纵坐标。最后原题转化为最长不下降子序列。
代码
#include#include #include #include #include #define ll long longusing namespace std;const char* fin="shield.in";const char* fout="shield.out";const ll inf=0x7fffffff;const ll maxn=200007;ll n,i,j,k;ll c[maxn];double ax,ay,bx,by;struct point{ double x,y,x1,y1;}a[maxn];double abs(double a){ return a>0?a:-a;}bool cmp(point a,point b){ if (abs(a.x-b.x)<10e-7) return a.y
启发
向量初步接触
向量*实数=一个放大或缩小的向量
向量+向量=遵循平行四边形定则的一个向量(参考力的合力) 利用单位向量表示一个向量。 平时见的平面直角坐标系就是以(1,0)和(0,1)为单位向量的坐标系。实数运算精度问题
尽量避免除法运算,譬如宁可乘以0.5也不除以2。
误差小于10e-7考虑当作是相等的两个实数。