#P4073. [WC2013] 平面图

    ID: 1021 远端评测题 5000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论计算几何2013倍增平衡树WC/CTSC/集训队枚举暴力生成树

[WC2013] 平面图

题目描述

在一个平面中有 nn 个顶点和 mm 条直线段,第 ii 个顶点的坐标为(xi,yi)(x_i, y_i), 第jj条直线段连接顶点 uju_j 和顶点 vjv_j,权值为 hjh_j, 除顶点 uju_jvjv_j 外直线段 jj 不经过其他的顶点。 任意两条直线段如果存在公共点,则该公共点一定是一个顶点,此时这两条直线段都会连接这个顶点。 对于任意的两个顶点 xxyy,总是可以找到一顶点序列 a1a_1, a2a_2, …, aka_k 使得 a1a_1 = xx, aka_k = yy 且对于任意 11ii < kk 满足 aia_iai+1a_{i+1}被一条直线段直接连接。

mm 条直线段将整个平面分成了若干个区域,其中只有一个区域是无穷大的,其余均是有界的,我们称无穷大的区域为禁区。

现在给出 qq 次询问,每次给定平面中的任意两个不是顶点且分别不在任意一条直线段上的点 AABB, 请画一条曲线连接 AABB,要求曲线不能经过禁区以及任何顶点,并使得穿过的直线段中权值最大的尽可能小。 你需要对每次询问回答这个值最小为多少。

输入格式

从文件 graph.in 中读入数据。

第一行有两个正整数 nnmm, 分别表示顶点数和直线段数。

接下来 nn 行,每行两个整数, 这部分中第 ii 行(总第 ii + 11 行) 的两个整数xix_iyiy_i 为顶点 ii 的坐标。

接下来 mm 行,每行三个正整数 uuvvhh, 表示有一条直线段连接顶点 uu 和顶点 vv,权值为 hh。 其中 uuvv

接下来的一行,有一个正整数 qq,表示询问数量。

接下来 qq 行,每行四个实数 AxA_xAyA_yBxB_xByB_y, 表示一组两个点的坐标分别为(Ax,Ay)(A_x, A_y)(Bx,By)(B_x, B_y)的询问。

输出格式

输出到文件 graph.out 中。

输出 qq 行,每行一个正整数,依次表示每个询问的答案。特别的,若不需要跨过任何一条边即可到达,请输出 00;若不存在合法的曲线,请输出-11

9 12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 2 10
2 3 10
3 6 10
6 9 10
9 8 10
8 7 10
7 4 10
4 1 10
2 5 3
5 8 2
5 6 4
4 5 1
3
1.5 1.5 2.5 2.5
1.5 2.5 2.5 1.5
0.5 0.5 1.5 1.5
2
3
-1

提示

【样例说明】

QQ20180112214336.png

【数据规模与约定】

本题共设有 1010 个测试点,每个测试点的规模与特征如下:

QQ20180112215357.png

对于全部数据,均满足 55nn, mm, qq100,000100,000,所有直线段的权值不会超过 10910^9。所有询问坐标均为不超过 10710^7 的实数,且保证是 0.50.5 的整数倍。