题目描述
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<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using 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<b.y;
else return a.x<b.x;
}
bool cmp1(point a,point b){
return a.y<b.y;
}
void change(ll x,ll y){
for (;x<=n;x+=x&-x) c[x]=max(y,c[x]);
}
ll getmax(ll x){
ll k=0;
for (;x;x-=x&-x) k=max(k,c[x]);
return k;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%lld",&n);
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
for (i=1;i<=n;i++){
double j,k;
scanf("%lf%lf",&j,&k);
a[i].x=(j*by-k*bx)/(ax*by-ay*bx);
a[i].y=(j*ay-k*ax)/(bx*ay-by*ax);
}
sort(a+1,a+n+1,cmp1);
a[1].y1=1;
for (i=2;i<=n;i++) if (a[i].y-a[i-1].y<10e-7) a[i].y1=a[i-1].y1;else a[i].y1=a[i-1].y1+1;
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++) change(a[i].y1,getmax(a[i].y1)+1);
k=getmax(n);
printf("%lld",k);
return 0;
}启发
向量初步接触
向量*实数=一个放大或缩小的向量
向量+向量=遵循平行四边形定则的一个向量（参考力的合力）
利用单位向量表示一个向量。
平时见的平面直角坐标系就是以(1,0)和(0,1)为单位向量的坐标系。
实数运算精度问题
尽量避免除法运算，譬如宁可乘以0.5也不除以2。
误差小于10e-7考虑当作是相等的两个实数。