303118: CF607E. Cross Sum
Memory Limit:512 MB
Time Limit:7 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Cross Sum
题意翻译
### 题目描述 给定平面直角坐标系上的 $n$ 条两两不重合的直线。定义**可重**点集 $\mathcal{I}$,其包含 $n$ 条直线两两的交点。如果某个点作为交点出现了多次,其在 $\mathcal{I}$ 中也会出现多次。 给出一个询问点 $(p,q)$ ,定义可重数集 $\mathcal{D}$,其包含 $\mathcal{I}$ 中的所有点与 $(p,q)$ 的欧几里得距离,如果某个数出现了多次其在 $\mathcal{D}$ 中也会出现多次。 现在给出 $n$ 条直线与询问点,请求出 $\mathcal{D}$ 中前 $m$ 小的数的和,相同的数需要计算多次。 ### 输入格式 第一行一个整数 $n$ 表示直线数量; 第二行三个整数 $x,y,m$,询问点为 $(\frac{x}{1000} , \frac{y}{1000})$,$m$ 意义如上所述; 接下来 $n$ 行每行两个整数 $a_i,b_i$ 表示一条直线 $y = \frac{a_i}{1000}x + \frac{b_i}{1000}$。 ### 输出格式 一行一个浮点数表示答案,相对或绝对误差不超过 $10^{-6}$ 时认为正确。 ### 数据范围 $2 \leq n \leq 5 \times 10^4$,$0 \leq |x|,|y|,|a_i|,|b_i| \leq 10^6$,$1 \leq m \leq \min\{3 \times 10^7 , |\mathcal{D}|\}$,$\forall i \neq j, (a_i,b_i) \neq (a_j,b_j)$。题目描述
Genos has been given $ n $ distinct lines on the Cartesian plane. Let ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/828bd1f150735aa8c65c79525d1418ab3058d668.png) be a list of intersection points of these lines. A single point might appear multiple times in this list if it is the intersection of multiple pairs of lines. The order of the list does not matter. Given a query point $ (p,q) $ , let ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/887c79cacd151e1b1341a67c48b05ad1977a6a94.png) be the corresponding list of distances of all points in ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/828bd1f150735aa8c65c79525d1418ab3058d668.png) to the query point. Distance here refers to euclidean distance. As a refresher, the euclidean distance between two points $ (x_{1},y_{1}) $ and $ (x_{2},y_{2}) $ is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/86b2aa253cbc7f8f2ad97ad58bb4a22991d5ff81.png). Genos is given a point $ (p,q) $ and a positive integer $ m $ . He is asked to find the sum of the $ m $ smallest elements in ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/887c79cacd151e1b1341a67c48b05ad1977a6a94.png). Duplicate elements in ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/887c79cacd151e1b1341a67c48b05ad1977a6a94.png) are treated as separate elements. Genos is intimidated by Div1 E problems so he asked for your help.输入输出格式
输入格式
The first line of the input contains a single integer $ n $ ( $ 2<=n<=50000 $ ) — the number of lines. The second line contains three integers $ x $ , $ y $ and $ m $ ( $ |x|,|y|<=1000000 $ , ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/8201e41b76d5859818b53fa92521eb060190c840.png)) — the encoded coordinates of the query point and the integer $ m $ from the statement above. The query point $ (p,q) $ is obtained as ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/ab5ed9d2a6b0c9e268daea47ead56f0338fbfe18.png). In other words, divide $ x $ and $ y $ by $ 1000 $ to get the actual query point. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/10e260f8817511999fbd109fdb87fbea4e756803.png) denotes the length of the list ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/887c79cacd151e1b1341a67c48b05ad1977a6a94.png) and it is guaranteed that ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/ee6d034e06de3830b228a5cd59532bc52e9dfb32.png). Each of the next $ n $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ |a_{i}|,|b_{i}|<=1000000 $ ) — the parameters for a line of the form: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/ea08f1eff68d58992a22c15cbd8926ac7afc12c5.png). It is guaranteed that no two lines are the same, that is $ (a_{i},b_{i})≠(a_{j},b_{j}) $ if $ i≠j $ .
输出格式
Print a single real number, the sum of $ m $ smallest elements of ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/887c79cacd151e1b1341a67c48b05ad1977a6a94.png). Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . To clarify, let's assume that your answer is $ a $ and the answer of the jury is $ b $ . The checker program will consider your answer correct if ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF607E/c5d4f85807f95b08a3db7aae534822038a5bf1df.png).
输入输出样例
输入样例 #1
4
1000 1000 3
1000 0
-1000 0
0 5000
0 -5000
输出样例 #1
14.282170363
输入样例 #2
2
-1000000 -1000000 1
1000000 -1000000
999999 1000000
输出样例 #2
2000001000.999999500
输入样例 #3
3
-1000 1000 3
1000 0
-1000 2000
2000 -1000
输出样例 #3
6.000000000
输入样例 #4
5
-303667 189976 10
-638 116487
-581 44337
1231 -756844
1427 -44097
8271 -838417
输出样例 #4
12953.274911829