# 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 阅读(902) 评论(1)  编辑 收藏 引用