学步园

题意：一个句型的大盒子，加上一定数量的隔板，划分为n个小盒子。

给某点坐标，判断该点是在哪个小盒子的范围内。

思路：叉积判断点是在隔板的哪一侧，二分搜索逐渐缩小范围。

#include <iostream><br /> using namespace std;<br /> int count[5005];<br /> struct Node<br /> {<br /> __int64 x,y;<br /> };<br /> struct Edge<br /> {<br /> Node up;<br /> Node low;<br /> }boundary[5005];<br /> inline __int64 CrossMutiply(Node p1,Node p2,Node p3)<br /> {<br /> return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);<br /> }<br /> int n,m;<br /> __int64 x1,x2;<br /> Node upper_left,lower_right,temp;<br /> void Add(Node& p)<br /> {<br /> int first=0,end=n+1,mid;<br /> while(end-first>1)<br /> {<br /> mid=(first+end)/2;<br /> if(CrossMutiply(boundary[mid].low,boundary[mid].up,p)>0) end=mid;<br /> else first=mid;<br /> }<br /> count[first]++;<br /> }<br /> int main()<br /> {<br /> while(scanf("%d",&n)&&n)<br /> {<br /> scanf("%d%I64d%I64d%I64d%I64d",&m,&upper_left.x,&upper_left.y,&lower_right.x,&lower_right.y);<br /> boundary[0].up.x=boundary[0].low.x=0;<br /> boundary[n+1].up.x=boundary[n+1].low.x=lower_right.x;<br /> for(int i=0;i<=n+1;i++)<br /> {<br /> boundary[i].low.y=lower_right.y;<br /> boundary[i].up.y=upper_left.y;<br /> }<br /> for(int i=1;i<=n;i++)<br /> {<br /> scanf("%I64d%I64d",&x1,&x2);<br /> boundary[i].up.x=x1;<br /> boundary[i].low.x=x2;<br /> }<br /> memset(count,0,sizeof(count));<br /> for(int i=0;i<m;i++)<br /> {<br /> scanf("%I64d%I64d",&temp.x,&temp.y);<br /> Add(temp);<br /> }<br /> for(int i=0;i<=n;i++)<br /> {<br /> printf("%d: %d/n",i,count[i]);<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />