A6441 | 「CodePlus 2017 12 月赛」寄蒜几盒
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
> R 姓出题人:第一次出 CodePlus 月赛,好紧脏,怎么才能装作经常出 CodePlus 月赛的样子?
> 某 W 姓出题人:写题面记得要加背景。
> R 姓出题人:可是我的题目没有什么背景可以写,怎么办?
> 某 W 姓出题人:其实背景和题面没有关系也是可以的。
> R 姓出题人:原来如此,那我知道了。
在二维平面上有 $n$ 条直线,这些直线会将平面划分成若干个区域。给定 $m$ 个点,求每个点所在的区域的面积。
聪明的读者会发现有些点所在的区域面积是无穷大的。R 姓出题人早就想到了这一点,所以他给出了一个实数 $L$,由额外的四条直线
$x=L,$ $x=-L,$ $y=L,$ $y=-L$ 框定了一个有限的平面区域,并且所有的询问点都在这个框定的平面区域内部。
聪明绝顶的读者会发现如果询问点恰好落在某条直线上或者离某条直线的距离非常近,那么精度误差会严重影响答案。R 姓出题人早就想到了这一点,所以在他造的数据中,任意一个询问点距离任意一条直线的距离大于 $10^{-7}$。
> 某 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$ 个点的坐标。
第一行两个正整数 $n,m$ 和一个正实数 $L$。
接下来 $n$ 行每行三个实数 $A,B,C$,表示这条直线的方程为 $Ax+By+C=0$。
接下来 $m$ 行,第$i$行两个实数 $x_i,y_i$,表示第 $i$ 个点的坐标。
输出格式
输出到标准输出。
输出 $m$ 行,每行一个实数,第 $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
感谢腾讯公司对此次比赛的支持。
对于40%的数据,$n,m\le300$
对于所有数据,$n\le500,m\le100000$,输入数据的绝对值 $\le10^7$,且输入数据最多保留两位小数。
---
来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/茹逸中 命题/茹逸中 验题/陈宇,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?