<div class="post_brief"><p>
简单的算几+网络流么。然后花了将近两天。最近总和算几过不去啊。</p>
判断线段和圆是否有交还是比较简单的。反正不要让我用解析。先找下垂线，然后找下垂足，然后点乘一下搞定。然后错得不知道怎么死的。搞了很久。
然后二分网络流水水水水水水水水。
感觉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());}