学步园

给你一个盒子，然后很多隔板，以及toys的坐标，问你每个隔板里有多少个玩具。

隔板是按从左到右给的，而且不会相交，所以区域就是n+1块。注意toy可以在边界上，但是不能在隔板上。

我直接枚举了，枚举每个点可能在哪个区域里，如果在这个区域里，一定满足在相对每个边来说是在左手边，这个判断用叉积就好了，用叉积判断时间复杂度是O（V）的。（刚才想了下，这个只能适用于凸多边形><）

后来党说可以用那个，发出一条射线，然后如果有奇数个交点说明在多边形内，这个之前见过，但是没写过，我这个1000+MS过了。。好慢啊。。。党说那个觉得蛮繁琐的，因为这个每个区域只有四个点，所以不需要判断那么多。。

1A，开心~

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm><br /> using namespace std;<br /> const int MAX = 5010;<br /> struct SEG{<br /> int x1,y1,x2,y2;<br /> };<br /> SEG s[MAX];<br /> struct point{<br /> int x,y;<br /> };<br /> point toy[MAX];<br /> int sum[MAX];<br /> int crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向<br /> {<br /> return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);<br /> }<br /> bool inBox(point t,SEG ls,SEG rs)<br /> {<br /> point a,b,c,d;<br /> a.x = ls.x1; a.y = ls.y1;<br /> b.x = ls.x2; b.y = ls.y2;<br /> c.x = rs.x2; c.y = rs.y2;<br /> d.x = rs.x1; d.y = rs.y1;<br /> if( crossProduct(b,t,c) >= 0 && crossProduct(c,t,d) >= 0<br /> && crossProduct(d,t,a) >= 0 && crossProduct(a,t,b) >= 0 )<br /> return true;<br /> return false;<br /> }<br /> int main()<br /> {<br /> int n,m,x1,y1,x2,y2,a,b;<br /> while( ~scanf("%d",&n) && n )<br /> {<br /> memset(sum,0,sizeof(sum));<br /> scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);<br /> s[0].x1 = x1; s[0].y1 = y1;<br /> s[0].x2 = x1; s[0].y2 = y2;<br /> for(int i=1; i<=n; i++)<br /> {<br /> scanf("%d %d",&a,&b);<br /> s[i].x1 = a; s[i].y1 = y1;<br /> s[i].x2 = b; s[i].y2 = y2;<br /> }<br /> n++;<br /> s[n].x1 = x2; s[n].y1 = y1;<br /> s[n].x2 = x2; s[n].y2 = y2;<br /> for(int i=0; i<m; i++)<br /> scanf("%d %d",&toy[i].x,&toy[i].y);<br /> for(int i=0; i<m; i++)<br /> for(int k=0; k<n; k++)<br /> if( inBox(toy[i],s[k],s[k+1]) )<br /> {<br /> sum[k]++;<br /> break;<br /> }<br /> for(int i=0; i<n; i++)<br /> printf("%d: %d/n",i,sum[i]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />