BZOJ1822 [JSOI2010]Frozen Nova 冷冻波

简单的算几+网络流么。然后花了将近两天。最近总和算几过不去啊。

判断线段和圆是否有交还是比较简单的。反正不要让我用解析。先找下垂线，然后找下垂足，然后点乘一下搞定。然后错得不知道怎么死的。搞了很久。

然后二分网络流水水水水水水水水。

感觉mac好卡啊，gdb巨卡，bash也非常卡。难道我又没有搞对打开方式？

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

inline long double sqr(long double x) {
	return x * x;
}

typedef struct geo_obj {
	double x, y;
	geo_obj() {}
	geo_obj(double x0, double y0) {
		x = x0, y = y0;
	}
	inline void read() {
		scanf("%lf%lf", &x, &y);
	}
	inline geo_obj rev() {
		return geo_obj(-y, x);
	}
	inline double len() {
		return sqrt(sqr(x) + sqr(y));
	}
	inline double sqLen() {
		return sqr(x) + sqr(y);
	}
} point, vect;
inline geo_obj operator +(const geo_obj& a, const geo_obj& b) {
	return geo_obj(a. x + b. x, a. y + b. y);
}
inline geo_obj operator -(const geo_obj& a, const geo_obj& b) {
	return geo_obj(a. x - b. x, a. y - b. y);
}
inline geo_obj operator *(const geo_obj& a, const double& b) {
	return geo_obj(a. x * b, a. y * b);
}
inline double operator *(const geo_obj& a, const geo_obj& b) {
	return a. x * b. y - a. y * b. x;
}
inline double operator &(const geo_obj& a, const geo_obj& b) {
	return a. x * b. x + a. y * b. y;
}

struct line {
	point p;
	vect v;
	line(point a, point b) {
		p = a;
		v = b - a;
	}
};
struct circle {
	point o;
	double r;
	void read() {
		o. read();
		scanf("%lf", &r);
	}
};

inline point lineCross(const line& a, const line& b) {
	vect w(b. p - a. p);
	double rat((w * a. v) / (a. v * b. v));
	return b. p + b. v * rat;
}

bool segInCircle(point a, point b, circle c) {
	line l(a, b);
	vect u(l. v. rev());
	line r(c. o, c. o + u);
	point p(lineCross(l, r));
	double x = (p - c. o). sqLen();
	double sr(sqr(c. r));
	if (x >= sr)
		return 0;
	if (((a - p) & (b - p)) <= 0)
		return 1;
	if ((a - c. o). sqLen() <= sr)
		return 1;
	if ((b - c. o). sqLen() <= sr)
		return 1;
	return 0;
}

struct edge {
	int t, c;
	edge *next, *rv;
};

struct wiz {
	point p;
	int r, t;
	void read() {
		p. read();
		scanf("%d%d", &r, &t);
	}
};

const int maxn = 409;
const int maxe = 80409;
const int inf = 0x3f3f3f3f;

int n, m, c, t, ea[maxe], eb[maxe], ou[maxn];
int d[maxn], st, te;
wiz w[maxn];
circle tree[maxn];
point spi[maxn];
edge elst[maxe], *ep, *head[maxn << 1];

inline edge* newEdge(int u, int v, int c) {
	ep-> t = v;
	ep-> c = c;
	ep-> next = head[u];
	head[u] = ep;
	return ep ++;
}
inline void addEdge(int u, int v, int c) {
	edge *a = newEdge(u, v, c);
	edge *b = newEdge(v, u, 0);
	a-> rv = b;
	b-> rv = a;
}

bool bfsBuild() {
	static int q[maxn];
	int hd(0), tl(1);
	memset(d, 0, sizeof(d));
	d[q[0] = st] = 1;
	while (hd < tl && !d[te]) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> c && !d[e-> t]) {
				d[e-> t] = d[p] + 1;
				q[tl ++] = e-> t;
			}
	}
	return d[te];
}
int dfsFind(int p, int c) {
	if (p == te)
		return c;
	int s(0);
	edge* e;
	for (e = head[p]; e && c; e = e-> next)
		if (e-> c && d[e-> t] == d[p] + 1) {
			int x(dfsFind(e-> t, min(e-> c, c)));
			s += x;
			c -= x;
			e-> c -= x;
			e-> rv-> c += x;
		}
	if (!e)
		d[p] = -1;
	return s;
}

int binSearch() {
	int l(0), r(5000000);
	st = n + m;
	te = st + 1;
	while (l < r) {
		int mid((l + r) >> 1);
		ep = elst;
		memset(head, 0, sizeof(head));
		for (int i = 0; i < t; ++ i)
			addEdge(ea[i], eb[i] + n, 1);
		for (int i = 0; i < n; ++ i)
			addEdge(st, i, (mid + w[i]. t) / w[i]. t);
		for (int i = 0; i < m; ++ i)
			addEdge(i + n, te, 1);
		int s(0);
		while (bfsBuild())
			s += dfsFind(st, inf);
		if (s == m)
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d%d", &n, &m, &c);
	for (int i = 0; i < n; ++ i)
		w[i]. read();
	for (int i = 0; i < m; ++ i)
		spi[i]. read();
	for (int i = 0; i < c; ++ i)
		tree[i]. read();
	memset(ou, 0, sizeof(ou));
	t = 0;
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < m; ++ j) {
			bool f(1);
			double ds(sqr(w[i]. p. x - spi[j]. x) + sqr(w[i]. p. y - spi[j]. y));
			if (ds > sqr(w[i]. r))
				f = 0;
			for (int k = 0; k < c && f; ++ k)
				if (segInCircle(w[i]. p, spi[j], tree[k]))
					f = 0;
			if (f) {
				ea[t] = i;
				eb[t] = j;
				++ t;
				ou[j] = 1;
			}
		}
	bool hs(1);
	for (int i = 0; i < m && hs; ++ i)
		if (!ou[i])
			hs = 0;
	if (!hs || !n)
		puts("-1");
	else
		printf("%d\n", binSearch());
}