第8届浙江省程序设计竞赛点评beta » ZOJ3495

ZOJ3495
ZOJ3495.cpp


#include <cmath>
#include <bitset>
#include <cstdio>
#include <algorithm>

using namespace std;

const double EPS = 1e-8;

inline int signum(double x) {
	if (x > EPS) {
		return 1;
	} else if (x < -EPS) {
		return -1;
	} else {
		return 0;
	}
}

struct Point{
    double x, y;
    Point() {}
    Point(double x, double y):x(x), y(y) {}
	double length() const { return hypot(x, y); }
};

Point operator+(const Point& lhs, const Point& rhs) {
	return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point operator-(const Point& lhs, const Point& rhs) {
	return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point operator*(double lhs, const Point& rhs) {
	return Point(lhs * rhs.x, lhs * rhs.y);
}

double operator/(const Point& lhs, const Point& rhs) {
	return lhs.x * rhs.y - lhs.y * rhs.x;
}

bool dotsInline(const Point& p1, const Point& p2, const Point& p3){
    return fabs((p1 - p3) / (p2 - p3)) < 0;
}

int decideSide(const Point& p1, const Point& p2, const Point& l1, const Point& l2){
    return signum((l1 - l2) / (p1 - l2)) * signum((l1 - l2) / (p2 - l2));
}

bool dotOnlineIn(const Point& p, const Point& l1, const Point& l2){
    return fabs((p - l2) / (l1 - l2)) < EPS && (l1.x - p.x) / (l2.x - p.x) < EPS && (l1.y - p.y) / (l2.y - p.y) < EPS;
}

bool intersectIn(const Point& u1, const Point& u2, const Point& v1, const Point& v2){
    if(!dotsInline(u1, u2, v1) || !dotsInline(u1, u2, v2))
        return decideSide(u1, u2, v1, v2) != 1 && decideSide(v1, v2, u1, u2) != 1;
    else
        return dotOnlineIn(u1, v1, v2) || dotOnlineIn(u2, v1, v2) || dotOnlineIn(v1, u1, u2) || dotOnlineIn(v2, u1, u2);
}

double disptoline(const Point& p, const Point& l1, const Point& l2){
    return fabs((p - l2) / (l1 - l2)) / (l1 - l2).length();
}

double disptoseg(const Point& p, const Point& l1, const Point& l2){
    Point t = Point(l1.y - l2.y, l2.x - l1.x);
    if(signum((l1 - p) / t) * signum((l2 - p) / t) > 0)
        return min((p - l1).length(), (p - l2).length());
    else
        return disptoline(p, l1, l2);
}

const int MAXN = 256;
Point a[MAXN], b[MAXN], c[MAXN];
double r[MAXN];
bitset<MAXN> lft[MAXN], rt[MAXN];

int main() {
	int re, n, m;
	Point p;
	bitset<MAXN> pre, cur;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf%lf", &c[i].x, &c[i].y, &r[i]);
		}
		for (int i = 0; i < m; ++i) {
			scanf("%lf%lf%lf%lf", &a[i].x, &a[i].y, &b[i].x, &b[i].y);
		}

		for (int i = 0; i < m; ++i) {
			p = .5 * (a[i] + b[i]);
			lft[i].reset();
			rt[i].reset();
			for (int j = 0; j < m; ++j) {
				lft[i].set(j, intersectIn(a[i], p, a[j], b[j]));
				rt[i].set(j, intersectIn(b[i], p, a[j], b[j]));
			}
			for (int j = 0; j < n; ++j) {
				lft[i].set(m + j, disptoseg(c[j], a[i], p) <= r[j] + EPS);
				rt[i].set(m + j, disptoseg(c[j], b[i], p) <= r[j] + EPS);
			}
		}

		cur.reset();
		for (int i = 0; i < n; ++i) {
			cur.set(m + i);
		}
		do {
			pre = cur;
			for (int i = 0; i < m; ++i) {
				if (cur.test(i)) {
					continue;
				}
				if ((lft[i] & cur).any() && (rt[i] & cur).any()) {
					cur.set(i);
				}
			}
		} while (cur != pre);

		puts((int)cur.count() == n + m ? "YES" : "NO");
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//476 	2011-04-15 01:52:29 	Accepted 	I 	C++ 	170 	208 	watashi 	Source
Leave a Reply