TOYS POJ - 2318(叉乘+二分)

TOYS
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 23275 Accepted: 10747

Description
Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John’s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input
The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output
The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

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

Hint
As the example illustrates, toys that fall on the boundary of the box are “in” the box.

运用叉乘求得点在各个间隔的左方还是右方（对于cross(vector(p2-p1),vector(p3-p1))<0则Point_p3位于直线p1p2的左方），每个隔间线段可以算作顺序排列，可用二分求出点右边第一个隔间线段（即存储区），统计各存储区的点数，具体见代码。

Ac Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<vector>
#include<iomanip>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e5 + 5;


#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))< EPS )

class Point
{
   
public:
	double x, y;
	Point(double x = 0, double y = 0) :x(x), y(y) {
   }
	Point operator + (Point p) {
    return Point(x + p.x, y + p.y); }
	Point operator - (Point p) {
    return Point(x - p.x, y - p.y); }
	Point operator * (double a) {
    return Point(a * x, a * y); }
	Point operator / (double a) {
    return Point(x / a, y / a); }

	double abs() {
    return sqrt(norm()); }
	double norm() {
    return x * x + y * y; }
	bool operator < (const Point& p)const
	{
   
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator == (const Point& p)const
	{
   
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};

typedef Point Vector;

struct Segment
{
   
	Point p1, p2;
	Segment(Point a, Point b) :p1(a), p2(b) {
   }
};
typedef Segment Line;

class Circle
{
   
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {
   }
};

typedef vector<Point> Polygon;

double dot(Vector a, Vector b)//点乘，求投影
{
   
	return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b)//叉乘，求面积
{
   
	return a.x * b.y - a.y * b.x;
}

bool isOrthogonal(Vector a, Vector b)//判断向量AB是否垂直
{
   
	return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2)
{
   
	return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2)
{
   
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

bool isParallel(Vector a, Vector b)
{
   
	return equals(cross(a, b), 0.0);
}

Point project(Segment s, Point p)//点在线段上的投影
{
   
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return s.p1 + base * r;
}

Point reflect(Segment s, Point p)//映像
{
   
	return p + (project(s, p) - p) * 2.0;
}

double getDistance(Point a, Point b)//两点之间的距离
{
   
	return (a - b).abs();
}

double getDistanceLP(Line l, Point p)//点到直线的距离
{
   
	return abs(cross(l.p2 - l.p1, p - l.p1) / (l.p2 - l.p1).abs());
}

double getDistanceSP(Segment s, Point p)//点到线段的距离
{
   
	if (dot(s.p2 - s.p1, p - s.p1) < 0.0)return (p - s.p1).abs();
	if (dot(s.p1 - s.p2, p - s.p2) < 0.0)return (p - s.p2).abs();
	return getDistanceLP(s, p);
}

int ccw(Point p0, Point p1, Point p2)
{
   
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) > EPS)return 1;//直线p0-p2在直线p0-p1的逆时针方向；
	if (cross(a, b) < -EPS)return -1;//直线p0-p2在直线p0-p1的顺时针方向；
	if (dot(a, b) < -EPS)return 2;//p2在p0-p1的后方
	if (a.norm() < b.norm())return -2;//p2在p0-p1的前方
	return 0;//p2在p0-p1上

}

bool intersect(Point p1, Point p2, Point p3, Point p4)//线段p1p2与线段p3p4是否相交
{
   
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}

bool intersect(Segment s1, Segment s2)//判断线段s1、s2是否相交
{
   
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

double getDistance(Segment s1, Segment s2)//两线段之间的距离
{
   
	if (intersect(s1, s2))return 0.0;
	return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
		min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

Point getCrossPoint(Segment s1, Segment s2)//线段s1与线段s2的交点
{
   
	Vector base = s2.p2 - s2.p1;
	double d1 = abs(cross(base, s1.p1 - s2.p1));
	double d2 = abs(cross(base, s1.p2 - s2.p1));
	double t = d1 / (d1 + d2);
	return s1.p1 + (s1.p2 - s1.p1) * t;
}

pair<Point, Point> getCrossPoints(Circle c, Line l)//求圆与直线的交点
{
   
	Vector pr = project(l, c.c);
	Vector e = (l.p2 - l.p1) / (l.p2 - l.p1).abs();
	double base = sqrt(c.r * c.r - (pr - c.c).norm());
	return make_pair(pr + e * base, pr - e * base);
}

double arg(Vector p) {
    return atan2(p.y, p.x); }
Vector polar(double a, double r) {
    return Point(cos(r) * a, sin(r) * a); }

pair<Point, Point> getCrossPoints(Circle c1, Circle c2)//圆与圆的交点
{
   
	double d = (c1.c - c2.c).abs();
	double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
	double t = arg(c2.c - c1.c);
	return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}

int contains(Polygon g, Point p)//内包 点在多边形内返回2，多边形上返回1，多边形外返回0
{
   
	int n = g.size();
	bool x = false;
	for (int i = 0;i < n;i++)
	{
   
		Point a = g[i] - p, b = g[(i + 1) % n] - p;
		if (abs(cross(a, b)) < EPS && dot(a, b) < EPS)return 1;
		if (a.y > b.y) swap(a, b);
		if (a.y < EPS && EPS<b.y && cross(a, b)>EPS)x = !x;
	}
	return (x ? 2 : 0);
}

Polygon andrewScan(Polygon s)//凸包
{
   
	Polygon u, l;
	if (s.size() < 3)return s;
	sort(s.begin(), s.end());
	//将x值最小的2个点添加至u
	u.push_back(s[0]);
	u.push_back(s[1]);
	//将x值最大的2个点添加至u
	l.push_back(s[s.size() - 1]);
	l.push_back(s[s.size() - 2]);

	//构建凸包上部
	for (int i = 2;i < s.size();i++)
	{
   
		for (int n = u.size();n >= 2 && ccw(u[n - 2], u[n - 1], s[i]) != -1;n--)
		{
   
			u.pop_back();
		}
		u.push_back(s[i]);
	}
	//构造凸包下部
	for (int i = s.size() - 3;i >= 0;i--)
	{
   
		for (int n = l.size();n >= 2 && ccw(l[n - 2], l[n - 1], s[i]) != -1;n--)
		{
   
			l.pop_back();
		}
		l.push_back(s[i]);
	}
	//按顺时针方向生成凸包的点的序列
	reverse(l.begin(), l.end());
	for (int i = u.size() - 2;i >= 1;i--)
	{
   
		l.push_back(u[i]);
	}
	return l;
}

int lst[Max];
int node[Max];
int door[Max];
int ban[Max][2];

bool check(Point a,Point b,Point c)
{
   
	if (ccw(a, b, c) == -1)return true;
	return false;
}

int main()
{
   
	FAST;
	int n, m, x1, y1, x2, y2;
	while (cin >> n >> m >> x1 >> y1 >> x2 >> y2)
	{
   
		memset(door, 0, sizeof(door));
		ban[0][0] = x1, ban[0][1] = x1, ban[n + 1][0] = x2, ban[n + 1][1] = x2;
		for (int i = 1;i <= n;i++)
		{
   
			cin >> ban[i][0] >> ban[i][1];
		}
		for (int i = 1;i <= m;i++)
		{
   
			int x, y;cin >> x >> y;
			int l = 0, r = n + 1, mid = (l + r) / 2;
			while (l <= r)
			{
   
				mid = (l + r) / 2;
				if (check(Point(ban[mid][0], y1), Point(ban[mid][1], y2), Point(x, y))) r = mid - 1;
				else l = mid + 1;
			}
			door[l - 1]++;
		}
		for (int i = 0;i <= n;i++)
		{
   
			cout << i << ": " << door[i] << endl;
		}
		cout << endl;
	}
}