2010福州网预的题目
M个点，向N个点发出射线，方向向量为同一向量。(M <= 10000,N <= 10000)坐标都是三维。
问这N个点中最多有多少个点被射中。
做法：排序+二分，O((M+N)logM)
因为方向向量的模恒不为0。那么就可以利用方向向量来投影。
将M个点投射到同一平面内（方向向量的三维，哪一维不为0，就投射到哪一维对应的品面），构造一个新的数据组，维护其他两维和放缩比例。然后将这个新数组排序。比较级为先p，后q，再val。
接下来，对N个点中的每个也按同样方式投射，二分查找在平面内的所在位置，判断所在位置是否与M个点中的某个点的投影重合，再判断放缩比例是否符合要求（放缩变量越大说明点越靠“后”），统计即可。
这题坑爹的卡STL，set、map均超时，用了lower_bound才过，而且竟然比我手写的二分还快。泪目。。卡了一年的题终于过了。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 10005
using namespace std;
int t,n,m;
const double eps = 1e-8;
int comp(double x)
{
return (fabs(x) < eps ? 0 : x < -eps ? -1: 1);
}
struct point
{
double x,y,z;
point(){}
point(double a,double b,double c):x(a),y(b),z(c){}
void read()
{
scanf("%lf %lf %lf",&x,&y,&z);
}
}cro[maxn],ene[maxn],vec;
struct sol
{
double x,y,val;
sol(){}
sol(double a,double b,double e):x(a),y(b),val(e){}
}s[maxn];
bool operator < (const sol a,const sol b)
{
return comp(a.x - b.x) < 0 || (comp(a.x - b.x) == 0 && comp(a.y - b.y) < 0) || (comp(a.x - b.x) == 0 && comp(a.y - b.y) == 0 && comp(a.val - b.val) < 0);
}
void gao()
{
scanf("%d %d",&n,&m);
double x,y,z;
for(int i = 1;i <= n;i++)
ene[i].read();
for(int i = 1;i <= m;i++)
cro[i].read();
vec.read();
int mod = 0;
if(comp(vec.x) != 0)
mod = 1;
else if(comp(vec.y) != 0)
mod = 2;
else if(comp(vec.z) != 0)
mod = 3;
for(int i = 1;i <= m;i++)
{
double temp;
double p,q;
switch(mod)
{
case 1:
temp = (0.0 - cro[i].x) / vec.x;
p = cro[i].y + temp * vec.y;
q = cro[i].z + temp * vec.z;
break;
case 2:
temp = (0.0 - cro[i].y) / vec.y;
p = cro[i].x + temp * vec.x;
q = cro[i].z + temp * vec.z;
break;
case 3:
temp = (0.0 - cro[i].z) / vec.z;
p = cro[i].x + temp * vec.x;
q = cro[i].y + temp * vec.y;
break;
}
s[i] = sol(p,q,temp);
}
sort(s + 1,s + m + 1);
int ans = 0;
for(int i = 1;i <= n;i++)
{
double temp,p,q;
switch(mod)
{
case 1:
temp = (0.0 - ene[i].x) / vec.x;
p = ene[i].y + temp * vec.y;
q = ene[i].z + temp * vec.z;
break;
case 2:
temp = (0.0 - ene[i].y) / vec.y;
p = ene[i].x + temp * vec.x;
q = ene[i].z + temp * vec.z;
break;
case 3:
temp = (0.0 - ene[i].z) / vec.z;
p = ene[i].x + temp * vec.x;
q = ene[i].y + temp * vec.y;
break;
}
sol *low = lower_bound(s + 1,s + m + 1,sol(p,q,temp));
for(sol * it = low;it != s + m + 1;it++)
{
if(comp(it -> x - p) != 0 || comp(it -> y - q) != 0)
break;
if(comp(it -> x - p) == 0 && comp(it -> y - q) == 0)
{
if(comp(it -> val - temp) >= 0)
{
ans++;
break;
}
}
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d",&t);
for(int i = 1;i <= t;i++)
{
printf("Case %d: ",i);
gao();
}
}