#6260. 「CodePlus 2017 12 月赛」寄蒜几盒

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

R 姓出题人:第一次出 CodePlus 月赛,好紧脏,怎么才能装作经常出 CodePlus 月赛的样子?
某 W 姓出题人:写题面记得要加背景。
R 姓出题人:可是我的题目没有什么背景可以写,怎么办?
某 W 姓出题人:其实背景和题面没有关系也是可以的。
R 姓出题人:原来如此,那我知道了。

在二维平面上有 n 条直线,这些直线会将平面划分成若干个区域。给定 m 个点,求每个点所在的区域的面积。

聪明的读者会发现有些点所在的区域面积是无穷大的。R 姓出题人早就想到了这一点,所以他给出了一个实数 L ,由额外的四条直线 x=L, x=-L, y=L, y=-L 框定了一个有限的平面区域,并且所有的询问点都在这个框定的平面区域内部。

聪明绝顶的读者会发现如果询问点恰好落在某条直线上或者离某条直线的距离非常近,那么精度误差会严重影响答案。R 姓出题人早就想到了这一点,所以在他造的数据中,任意一个询问点距离任意一条直线的距离大于 10^{-7}

输入格式

从标准输入读入数据。

第一行两个正整数 n,m 和一个正实数 L

接下来 n 行每行三个实数 A,B,C ,表示这条直线的方程为 Ax+By+C=0

接下来 m 行,第 i 行两个实数 x_i,y_i ,表示第 i 个点的坐标。

输出格式

输出到标准输出。

输出 m 行,每行一个实数,第 i 行输出的实数表示第 i 个点所在的区域的面积。保留两位小数。

样例

样例1输入

2 4 3
1 1 -1
-1 1 -1
0 2
-2 1
2 1
0 0

样例1输出

4.00
8.50
8.50
15.00

数据范围与提示

对于20%的数据, n,m\le10

对于40%的数据, n,m\le300

对于所有数据, n\le500,m\le100000 ,输入数据的绝对值 \le10^7 ,且输入数据最多保留两位小数。


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/茹逸中 命题/茹逸中 验题/陈宇,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。