どういう場合に到達不可能になるのかを考える。
センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。
全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。
やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。
#include <algorithm>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)
#define unless(cond) if (!(cond))
using namespace std;
typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;
struct E {
int a, b;
double cost;
E (int a_, int b_, double c)
: a(a_), b(b_), cost(c) {}
};
inline
bool operator < (const E& a, const E& b)
{
return a.cost < b.cost;
}
class UniotFind{
public:
vector<int> rank, p;
UniotFind (int size)
{
for (int i = 0; i < size; ++i) {
rank.push_back(0);
p.push_back(i);
}
}
void join(int a, int b)
{
link(find(a), find(b));
}
int find(int a)
{
return (a == p[a])? a : p[a] = find(p[a]);
}
bool is_same_set(int a, int b)
{
return find(a) == find(b);
}
void link (int a, int b)
{
if(rank[a] > rank[b]) p[b] = a;
else {
p[a] = b;
if(rank[a] == rank[b]) rank[b]++;
}
}
};
const int K = 300 + 1;
pair<int, int> p[K];
double g[K][K];
inline
double m_dist(int i1, int j1, int i2, int j2)
{
return abs(i1 - i2) + abs(j1 - j2);
}
double mst(const int N, const int sensor)
{
const int base = sensor;
const int W = 4 * 10000 + 1;
static pair<int, int> wall[W];
int M = 0;
wall[M++] = make_pair(0, N-1);
wall[M++] = make_pair(N-1, 0);
for (int i = 0; i < sensor; ++i) {
int x = p[i].first;
int y = p[i].second;
pair<int, int> ps[4] = {make_pair(x, 0), make_pair(0, y), make_pair(x, N-1), make_pair(N-1, y)};
for (int j = 0; j < 4; ++j) {
if (ps[j].first == 0 && ps[j].second == 0) continue;
if (ps[j].first == N-1 && ps[j].second == N-1) continue;
wall[M++] = ps[j];
}
}
int V = M + sensor;
const int T = V++;
const int B = V++;
const int R = V++;
const int L = V++;
const int V1 = V++;
const int V2 = V++;
vector<E> es;
es.push_back(E(V1, T, 0));
es.push_back(E(V1, L, 0));
es.push_back(E(V2, B, 0));
es.push_back(E(V2, R, 0));
for (int i = 0; i < sensor; ++i) {
for (int j = i + 1; j < sensor; ++j) {
es.push_back(E(i, j, g[i][j]));
}
}
for (int i = 0; i < sensor; ++i) {
for (int j = 0; j < M; ++j) {
int dist = m_dist(p[i].first, p[i].second, wall[j].first, wall[j].second);
es.push_back(E(i, j + base, dist));
}
}
UniotFind uf(V);
for (int i = 0; i < M; ++i) {
if (wall[i].first == 0) uf.join(L, i + base);
if (wall[i].first == N - 1) uf.join(R, i + base);
if (wall[i].second == 0) uf.join(B, i + base);
if (wall[i].second == N - 1) uf.join(T, i + base);
}
double mn = 1e128;
for (int i = 0; i < sensor; ++i) {
mn = min(mn, m_dist(0, 0, p[i].first, p[i].second));
mn = min(mn, m_dist(N-1, N-1, p[i].first, p[i].second));
}
sort(es.begin(), es.end());
each (e, es) {
if (!uf.is_same_set(e->a, e->b)) {
uf.join(e->a, e->b);
if (uf.is_same_set(V1, V2)) return min(mn, e->cost);
}
}
return mn;
}
int main(int argc, char *argv[])
{
int tc;
cin >> tc;
while (tc--) {
int n, m;
cin >> n >> m;
pair<int, double> prob[m];
for (int i = 0; i < m; ++i) {
cin >> prob[i].first >> prob[i].second;
}
int mn = n * 2;
int size = 0;
for (int i = 0; i < K; ++i) {
pair<int, int> q;
cin >> q.first;
if (q.first == -1) break;
cin >> q.second;
p[size++] = q;
mn = min(mn, q.first + q.second);
}
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
g[i][j] = m_dist(p[i].first, p[i].second, p[j].first, p[j].second) / 2.0;
}
}
const double mx = mst(n, size);
double sum = 0;
for (int i = 0; i < m; ++i) {
if (prob[i].first < mx) sum += prob[i].second;
}
cout << sum << endl;
}
return 0;
}
