poj1741，poj 2318 TOYS

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;
}

?