POJ 2318 TOYS && POJ 2398 Toy Storage

读懂题是关键。

POJ2318 TOYS

题目大意：有一个大箱子，由n个板分为n+1块，标号为0~n已知盒子左上角和右下角的坐标及每个板上下两端的横坐标（板不会交错，且按顺序给出）然后给出玩具的坐标，统计每块空间内玩具个数（保证玩具一定落在空间内）。

第一行输入 n m x1 y1 x2 y2，分别为n个木板，m个玩具，矩形左上角坐标（x1，y1），右下角坐标（x2，y2）；接着输入n组数据，每组数据表示每个木板与矩形上边交点的横坐标以及下边交点的横坐标；继续输入m组数据，表示各个玩具的坐标。

这里实际就是判断点与线段的关系，利用叉积求取，同时利用二分找到对应的线段。

叉积p1×p2 = x1y2 - x2y1 = - p2×p1，若p1×p2为正，则相对于原点(0,0)来说，p1位于p2顺时针方向；若p1×p2为负，p1位于p2逆时针方向；若为0则方向相同，或相反。

具体代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct Point {
    int x, y;
};

struct Line {
   Point a, b;
} line[5005];

int cnt[5005];

int Multi(Point p1, Point p2, Point p0) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

int main()
{
    int n, m, x1, y1, x2, y2;
    int i, t1, t2;
    Point a;

    while (cin >>n&& n) {
        cin >> m >> x1 >> y1 >> x2 >> y2;
        for (i = 0; i < n; i++) {
            cin >> t1 >> t2;
            line[i].a.x = t1;
            line[i].a.y = y1;
            line[i].b.x = t2;
            line[i].b.y = y2;
        }
        memset(cnt, 0, sizeof (cnt));
        for (i = 0; i < m; i++) {
            cin >> a.x >> a.y;
            int l, r, mid;
            l = 0; r = n-1;
            while (l < r) {
                mid = (l + r) >> 1;
                if (Multi(a, line[mid].a, line[mid].b) > 0) l = mid + 1;
                else r = mid;
            }
            if (Multi(a, line[l].a, line[l].b) < 0) cnt[l]++;
            else cnt[l+1]++;
        }
        for (i = 0; i <= n; i++)
            printf ("%d: %d
", i, cnt[i]);
        printf("
");
    }
    return 0;
}

POJ2398 Toy Storage

原题地址：http://poj.org/problem?id=2398

题目大意与POJ2318差不多，只是在POJ2318中木板上下两端的横坐标顺序给出，POJ2389自己排一下序即可，同时输出也有不同，统计一下输出就ok啦。

具体代码实现：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

struct Point{
	long long int x, y;
};

struct Line{
	Point a, b;
} line[5005];

long long int cnt[1005], cnt1[1010];

int Multi(Point p1, Point p2, Point p0){
	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

bool comp (Line a, Line b){
	return a.a.x < b.a.x;
}

int main()
{
	int n, m, x1, y1, x2, y2;
	int i, t1, t2;
	Point a;

	while (cin >> n && n){
		cin >> m >> x1 >> y1 >> x2 >> y2;
		for (i = 0; i < n; i++){
			cin >> t1 >> t2;
			line[i].a.x = t1;
			line[i].a.y = y1;
			line[i].b.x = t2;
			line[i].b.y = y2;
		}

		sort(line, line + n, comp);
		memset(cnt, 0, sizeof (cnt));
		memset(cnt1, 0, sizeof(cnt1));
		for (i = 0; i < m; i++){
			cin >> a.x >> a.y;
			int l, r, mid;
            l = 0; r = n - 1;
            while (l < r){
                mid = (l + r) >> 1;
                if (Multi(a, line[mid].a, line[mid].b) > 0)
                    l = mid + 1;
                else
                    r = mid;
            }
            if (Multi(a, line[l].a, line[l].b) < 0)
                cnt[l]++;
            else
                cnt[l + 1]++;
		}

		cout << "Box" << endl;
		for (int i = 0; i <= n; i++){
			if (cnt[i]){
				cnt1[cnt[i]]++;
			}
		}
		for (int i = 1; i <= m; i++){
			if (cnt1[i]){
				printf("%d: %I64d
", i, cnt1[i]);
			}
		}
	}
	return 0;
}