【叉积+二分】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[5005];
double U[5005], L[5005];
int res[5005];

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[n] = L[n] = x2;    //加最后一条边（矩型的右边），二分有用

/***********************************华丽的分割线***********************************/

		//下面是利用 叉积+二分 查找点所在位置，二分太强大了
		memset (res, 0, sizeof(res));
		for (i = 0; i < m; i++)
		{
			scanf ("%lf%lf", &p[i].x, &p[i].y);    //输入要找的点
			l = 0, r = n;
			while (l < r)
			{
				mid = (l + r) / 2;
				point b(L[mid], y2), c(U[mid], y1);    //第mid条分割线bc
				if (multi (p[i], b, c) > 0)
					r = mid;
				else l = mid + 1;
			}
			mid = (l + r) / 2;
			res[mid]++;    //得知此点在第mid个区间
		}
		for (i = 0; i <= n; i++)
			printf ("%d: %d\n", i, res[i]);
	}
	return 0;
}

评论

2 楼 基德KID.1412 2011-08-07  

sgeteternal 写道

1 楼 sgeteternal 2011-08-07