Description

WJJ 喜欢 “魔兽争霸” 这个游戏. 在游戏中, 巫妖是一种强大的英雄, 它的技能 Frozen Nova 每次可以杀死一个小精灵. 我们认为, 巫妖和小精灵都可以看成是平面上的点. 当巫妖和小精灵之间的直线距离不超过 \(R\), 且巫妖看到小精灵的视线没有被树木阻挡 (也就是说, 巫妖和小精灵的连线与任何树木都没有公共点) 的话, 巫妖就可以瞬间杀灭一个小精灵. 在森林里有 \(n\) 个巫妖, 每个巫妖释放 Frozen Nova 之后, 都需要等待一段时间, 才能再次施放. 不同的巫妖有不同的等待时间和施法范围, 但相同的是, 每次施放都可以杀死一个小精灵. 现在巫妖的头目想知道, 若从 \(0\) 时刻开始计算, 至少需要花费多少时间, 可以杀死所有的小精灵?

Input

输入文件第一行包含三个整数 \(n, m, k\), 分别代表巫妖的数量、小精灵的数量和树木的数量.

接下来 \(n\) 行, 每行包含四个整数 \(x, y, r, t\), 分别代表了每个巫妖的坐标、攻击范围和施法间隔 (单位为秒).

再接下来 \(m\) 行, 每行两个整数 \(x, y\), 分别代表了每个小精灵的坐标.

再接下来 \(k\) 行, 每行三个整数 \(x, y, r\), 分别代表了每个树木的坐标.

Output

输出一行, 为消灭所有小精灵的最短时间 (以秒计算). 如果永远无法消灭所有的小精灵, 则输出-1.

Sample Input

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output

5

Data Range

对于所有的数据, 满足:\(1 \leq n, m, k \leq 200\).

输入数据中所有坐标范围绝对值不超过 \(10000\), 半径和施法间隔不超过 \(20000\).

Explanation

首先用计算几何预处理出每个巫妖能看到哪几只精灵, 然后二分总时间, 用总时间除以发射间隔 (上取整) 得到流量限制, 然后网络流判断, 得到结果.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 256, maxm = 500100;
const int infinit = 0x7f7f7f7f;

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn<<1], epool[maxm];
    int level[maxn<<1];
    void add_edge(int u, int v, int flow, int revflow = 0)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->flow = revflow;
        q->next = edges[v]; edges[v] = q;
        p->rev = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        level[s] = 1;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] <= 0)
            return false;
        return true;
    }
    int find(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
    void init(void)
    {
        n = s = t = ecnt = 0;
        memset(edges, 0, sizeof(edges));
        return ;
    }
} graph;

struct point {
    int x, y;
    point(void) {
        x = y = 0; }
    point(int _1, int _2) {
        x = _1, y = _2; }
}; struct line {
    point a, b;
    line(void) { }
    line(point _1, point _2) {
        a = _1, b = _2; }
}; point operator + (point a, point b) {
    return point(a.x + b.x, a.y + b.y);
} point operator - (point a, point b) {
    return point(a.x - b.x, a.y - b.y);
} llf operator * (point a, point b) { // cross
    return a.x * b.y - a.y * b.x;
} llf dot(point a, point b) { // dot
    return a.x * b.x + a.y * b.y;
} llf dist(point a, point b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
} llf dist(line l, point p) {
    if (dot(l.a - p, l.b - p) > 0)
        return min(dist(l.a, p), dist(l.b, p));
    return fabs((p - l.a) * (l.b - l.a) / dist(l.a, l.b));
}

int n, m, K, max_tm;
point w[maxn], s[maxn], t[maxn]; // witch, fairy, tree
int r[maxn], tim[maxn], tr[maxn]; // radius, time, tree_radius
bool visible[maxn][maxn], removable[maxn];

bool check_visibility(int x, int y)
{
    if (dist(w[x], s[y]) > r[x])
        return false;
    rep(i, 1, K)
        if (dist(line(w[x], s[y]), t[i]) < tr[i])
            return false;
    return true;
}

int get_result(void)
{
    // That means some fairies are never reachable
    for (int i = 1; i <= m; i++)
        if (!removable[i])
            return -1;
    // And binary search with Dinic
    int l = 0, r = m * max_tm;
    while (l <= r) {
        int mid = (l + r) / 2;
        // Building graph
        graph.init();
        graph.n = n + m + 1;
        graph.s = 0; // graph.n - 1;
        graph.t = graph.n;
        rep(i, 1, n)
            graph.add_edge(graph.s, i, mid / tim[i] + 1);
        rep(i, 1, m)
            graph.add_edge(i + n, graph.t, 1);
        rep(i, 1, n) rep(j, 1, m)
            if (visible[i][j])
                graph.add_edge(i, j + n, 1);
        // Checking
        int res = graph.eval();
        if (res < m)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &K);
    rep(i, 1, n) {
        scanf("%d%d%d%d", &w[i].x, &w[i].y, &r[i], &tim[i]);
        max_tm = max(max_tm, tim[i]);
    }
    rep(i, 1, m)
        scanf("%d%d", &s[i].x, &s[i].y);
    rep(i, 1, K)
        scanf("%d%d%d", &t[i].x, &t[i].y, &tr[i]);
    // Can you see those trees?
    rep(i, 1, n) rep(j, 1, m) {
        visible[i][j] = check_visibility(i, j);
        if (visible[i][j])
            removable[j] = true;
    }
    // Getting result
    int res = get_result();
    printf("%d\n", res);
    return 0;
}