题目描述

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考虑当作是相等的两个实数。