The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2318 toys 叉积的简单运用

题目意思很简单,把一个盒子分成很多部分,往盒子里扔小球,小球的落点当然要告诉你拉,让你统计每个盒子里最后拥有的小球数。
我的做法是叉积+二分。
#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

struct Point 
{              // 二维点或矢量 
    double x, y;  
    Point() 
{} 
    Point(
double x0, double y0): x(x0), y(y0) {} 
}


struct Line
 
{               // 二维的直线或线段 
    Point p1, p2; 
    Line() 
{} 
    Line(Point p10, Point p20): p1(p10), p2(p20) 
{} 
}



double multiply(Point sp,Point ep,Point op)
{
    
return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}




Line myline[
5100];
int record[5100];


int main()
{

    
int n,m,i;
    Point left;
    Point right;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        memset(record,
0,sizeof(record));
        scanf(
"%d%lf%lf%lf%lf",&m,&left.x,&left.y,&right.x,&right.y);
        myline[
0].p1.x=left.x;
        myline[
0].p1.y=right.y;
        myline[
0].p2.x=left.x;
        myline[
0].p2.y=left.y;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf",&myline[i].p2.x,&myline[i].p1.x);
            myline[i].p1.y
=right.y;
            myline[i].p2.y
=left.y;

        }

        myline[n
+1].p1.x=right.x;
        myline[n
+1].p1.y=right.y;
        myline[n
+1].p2.x=right.x;
        myline[n
+1].p2.y=left.y;
        
        Point toy;
        
for(i=1;i<=m;i++)
        
{
            scanf(
"%lf%lf",&toy.x,&toy.y);
            
int front=0;
            
int rear=n+1;
            
while(front<=rear)
            
{

                
int mid=(front+rear)>>1;
                
if(multiply(toy,myline[front].p2,myline[front].p1)>0&&multiply(toy,myline[mid].p2,myline[mid].p1)<0)
                
{

                    
if(mid==front+1)
                    
{
                        record[front]
++;
                        
break;
                    }

                    rear
=mid;
                    
continue;
                }

                
else
                
{

                    
if(mid+1==rear)
                    
{
                        record[mid]
++;
                        
break;
                    }

                    front
=mid;
                    
continue;
                }


            }

        }


        
for(i=0;i<=n;i++)
        
{
            printf(
"%d: %d\n",i,record[i]);
        }

        printf(
"\n");
    }

    
return 0;
}


恭喜此题成为我收集计算几何模板的第一题 呵呵~

posted on 2009-08-04 16:26 abilitytao 阅读(866) 评论(1)  编辑 收藏 引用

评论

# re: POJ 2318 toys 叉积的简单运用 2010-09-23 11:34 rayafjyblue

为什么要用二分,怎么用二分啊。。。没看懂。。。我用int写wa了,改用double过了,大概的数范围的问题。。。  回复  更多评论   


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