FZU 1981 Three Kingdoms 【排序+二分】

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 ? -11);
}
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();
    }
}

posted on 2011-09-02 20:06 BUPT-[aswmtjdsj] @ Penalty 阅读(197) 评论(0)  编辑 收藏 引用 所属分类: 计算几何FZU Solution Report


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜