【叉积+二分】POJ 2318 TOYS
http://poj.org/problem?id=2318题意：求每个被割线分离的区间内各有多少个点？
Sample Input
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0
Sample Output
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1
0: 2
1: 2
2: 2
3: 2
4: 2
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;struct point{ //点的结构double x, y;point (double a = 0, double b = 0){x = a, y = b;}}p;double U, L;int res;double multi (point a, point b, point c) //叉积判断点线关系{double x1, y1, x2, y2;x1 = b.x - a.x;y1 = b.y - a.y;x2 = c.x - b.x;y2 = c.y - b.y;return x1*y2 - x2*y1;}int main(){int n, i, m, l, r, mid, cc = 1;double x1, y1, x2, y2;while (scanf ("%d", &n), n){if (cc == 2)printf ("\n");cc = 2;scanf ("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);for (i = 0; i < n; i++)scanf ("%lf%lf", U+i, L+i); //输入分割线的上端+下端的横坐标U = L = x2; //加最后一条边（矩型的右边），二分有用/***********************************华丽的分割线***********************************///下面是利用 叉积+二分 查找点所在位置，二分太强大了memset (res, 0, sizeof(res));for (i = 0; i < m; i++){scanf ("%lf%lf", &p.x, &p.y); //输入要找的点l = 0, r = n;while (l < r){mid = (l + r) / 2;point b(L, y2), c(U, y1); //第mid条分割线bcif (multi (p, b, c) > 0)r = mid;else l = mid + 1;}mid = (l + r) / 2;res++; //得知此点在第mid个区间}for (i = 0; i <= n; i++)printf ("%d: %d\n", i, res);}return 0;}
页:
[1]