学步园

二维平面上点与线段关系的判定

     问题的基本模型是：已知平面上一线段AB，判定平面上一点C相对于AB的位置（C不和AB共线）。

通过向量叉积来判定线段与点的的位置关系。

   例题：Toys (http://poj.org/problem?id=2318)

//判断点于线段的位置关系<br /> #include<iostream><br /> #include<cstdio><br /> #include<stdlib.h><br /> # define N 5010<br /> using namespace std;<br /> typedef struct Node<br /> {<br /> int x,y;<br /> }Point;<br /> Point up[N],dw[N];<br /> int ans[N],cnt;<br /> int cross(Point a,Point b,Point o)<br /> {<br /> return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);<br /> }<br /> int find(Point t)<br /> {<br /> for(int i=0;i<cnt-1;i++)<br /> if(cross(t,up[i],dw[i])>0 && cross(t,up[i+1],dw[i+1])<0)<br /> return i;<br /> }<br /> int main()<br /> {<br /> int n,m,x1,y1,x2,y2;<br /> while(scanf("%d",&n),n)<br /> {<br /> scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);<br /> cnt=0;<br /> up[cnt].x=x1;up[cnt].y=y1;<br /> dw[cnt].x=x1;dw[cnt++].y=y2;<br /> for(int i=0;i<n;i++)<br /> {<br /> int u,l;<br /> scanf("%d%d",&u,&l);<br /> up[cnt].x=u;up[cnt].y=y1;<br /> dw[cnt].x=l;dw[cnt++].y=y2;<br /> }<br /> up[cnt].x=x2;up[cnt].y=y1;<br /> dw[cnt].x=x2;dw[cnt++].y=y2;<br /> memset(ans,0,sizeof(ans));<br /> Point t;<br /> for(int i=0;i<m;i++)<br /> {<br /> scanf("%d%d",&t.x,&t.y);<br /> ans[find(t)]++;<br /> }<br /> for(int i=0;i<cnt-1;i++)<br /> printf("%d: %d/n",i,ans[i]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }