TOYS
題意:給定一個如上的長方形箱子,中間有n條線段,將其分為n+1個區域,給定m個玩具的坐標,統計每個區域中的玩具個數。
思路:這道題很水,只是要知道會使用叉乘來表示點在線的上面還是下面;
當a.Xmult(b,c) < 0時,表示在線的上面。之后就是二分的時候,不能直接使用mid來ans[mid]++;
因為只是確定點在這條線的兩邊,到底是哪一邊,具體還要用tmp來判斷;(模板題)
poj1741、?
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define MS0(a) memset(a,0,sizeof(a)) const int MAXN = 5050; struct point{int x,y;point(){}point(int _x,int _y){x = _x; y = _y;}long long operator *(const point &b)const{// 叉乘return (1LL*x*b.y - 1LL*y*b.x);}point operator -(const point &b)const{return point(x - b.x,y - b.y);}long long dot(const point &b){ //點乘return 1LL*x*b.x + 1LL*y*b.y;}double dist(const point &b){return sqrt(1LL*(x-b.x)*(x-b.x)+1LL*(y-b.y)*(y-b.y));}long long dist2(const point &b){return 1LL*(x-b.x)*(x-b.x)+1LL*(y-b.y)*(y-b.y);}double len(){return sqrt(1LL*x*x+1LL*y*y);}double point_to_segment(point b,point c)//點a到“線段” bc的距離a.point_to_segment(b,c); {point v[4];v[1] = {c.x - b.x,c.y - b.y};v[2] = {x - b.x,y - b.y};v[3] = {x - c.x,y - c.y};if(v[1].dot(v[2]) < 0) return v[2].len();if(v[1].dot(v[3]) > 0) return v[3].len();return fabs(1.*(v[1]*v[2])/v[1].len());}long long Xmult(point b,point c){ // 當a->b與a->c順時針轉時,返回正;return (b-*this)*(c-*this);}void input(){scanf("%d%d",&x,&y);} }p[MAXN];struct Line{point s,t;Line(){}Line(point _s,point _t){s = _s,t =_t;} }line[MAXN]; int ans[MAXN]; int main() {int n,m,i,j,x1,y1,x2,y2,kase = 0,U,L;while(scanf("%d",&n),n){MS0(ans);if(kase) puts("");else kase++;scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);for(i = 1;i <= n;i++){scanf("%d%d",&U,&L);line[i] = Line(point(U,y1),point(L,y2));}line[0] = Line(point(x1,y1),point(x1,y2));int x,y;for(i = 0;i < m;i++){scanf("%d%d",&x,&y);int l = 0, r = n,mid,tmp;while(l <= r){mid = l + r >> 1;if( point(x,y).Xmult(line[mid].s,line[mid].t) < 0) r = mid-1; //在線的上邊else tmp = mid,l = mid+1; //線下的點所在的區域才是改line的標號; }ans[tmp]++;}for(i = 0;i <= n;i++){printf("%d: %d\n",i,ans[i]);}}return 0; }
?