POJ 3218 TOYS（计算几何）（二分）

POJ 3218 TOYS（计算几何）（二分）2015-02-25TOYS：http://poj.org/problem？id=2318

大意：给你一个箱子，有n个挡板分隔成n+1部分，给你m个玩具的坐标，问每一部分有几个玩具。

思路：举对每个玩具，二分线段下标，判断玩具在线段左边还是右边，枚举后统计。

#include <map>#include <stack>#include <queue>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <iostream>#include <limits.h>#include <algorithm>#define LL long long#define max（a,b） （（a）>（b）？（a）:（b））#define min（a,b） （（a）<（b）？（a）:（b））#define max3（a, b, c） （a>b？max（a, c）:max（b, c））#define min3（a, b, c） （a<b？min（a, c）:min（b, c））#define max4（a, b, c, d） max（max（a, b）, max（c, d））#define min4（a, b, c, d） min（min（a, b）, min（c, d））#define eps 1e-9#define INF 1 << 30using namespace std;int n, m;int cnt[5010];struct Point{int x, y;} P;struct node{Point a, b;} Line[5010];int Location（Point a, Point b, Point c）{return （a.x-c.x）*（b.y-c.y） - （b.x-c.x）*（a.y-c.y）;}void Binary_Search（Point a, int n）{int l, r, mid;l = 0;r = n-1;while（l < r）{mid = （l+r）>>1;if（Location（a, Line[mid].a, Line[mid].b） > 0）{l = mid+1;}else{r = mid;}}if（Location（a, Line[l].a, Line[l].b） < 0）{cnt[l]++;}else{cnt[l+1]++;}}void Solve（）{int x1, x2, y1, y2, t1, t2;while（~scanf（"%d", &n） && n）{memset（cnt, 0, sizeof（cnt））;scanf（"%d%d%d%d%d", &m, &x1, &y1, &x2, &y2）;for（int i = 0; i < n; ++i）{scanf（"%d%d", &t1, &t2）;Line[i].a.x = t1;Line[i].a.y = y1;Line[i].b.x = t2;Line[i].b.y = y2;}for（int i = 0; i < m; ++i）{scanf（"%d%d", &P.x, &P.y）;Binary_Search（P, n）;}for（int i = 0; i <= n; ++i）{printf（"%d: %d
", i, cnt[i]）;}printf（"
"）;}}int main（void）{freopen（"data.in", "r", stdin）;//freopen（"data.out", "w", stdout）;Solve（）;return 0;}

From：cnblogs GLsilence