Cuber QQ used to encounter such a problem: find the intersection of two infinitely long convex right prisms AA and BB. Actually this problem is also on HDU Online Judge, you can solve it afterwards if you are interested.
Cuber QQ quickly solved it, and thought it too easy because his program can handle more than that. So he modify it a little bit, by removing the constraints of ``convex'', that is, the cross-section of these two prisms are not necessarily convex, but they are still simple.
Formally, you have to find the volume of intersection of two prisms, whose cross-sections are both simple polygons. All joining edges of AA are parallel to the zz-axis, and all joining edges of BB are parallel to the xx-axis. If A and B do not intersect, the answer is 00 of course.
3037: Intersection of Prisms
| Time Limit | $7$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
The first line is an integer tt, denoting the number of test cases follows.
For each test case, there are two polygons, the base polygon of AA and BBrespectively.
An integer nn (3≤n≤1053≤n≤105) followed by nn lines, each containing two space-separated integers (x,y)(x,y) (−106≤x,y≤106−106≤x,y≤106), is the representation of the base polygon of AA. The following m+1m+1 (3≤m≤1053≤m≤105) gives a similar representation for BB, except that the coordinates given are (y,z)(y,z) (−106≤x,y≤106−106≤x,y≤106).
Each polygon are given in either clockwise or counterclockwise order. Following the convention, polygon PP is simple, if no two edges have any points in common, with the obvious exception of two consecutive segments having one common point.
The sum of m+nm+n from all test cases does not exceed 2⋅1062⋅106.
For each test case, there are two polygons, the base polygon of AA and BBrespectively.
An integer nn (3≤n≤1053≤n≤105) followed by nn lines, each containing two space-separated integers (x,y)(x,y) (−106≤x,y≤106−106≤x,y≤106), is the representation of the base polygon of AA. The following m+1m+1 (3≤m≤1053≤m≤105) gives a similar representation for BB, except that the coordinates given are (y,z)(y,z) (−106≤x,y≤106−106≤x,y≤106).
Each polygon are given in either clockwise or counterclockwise order. Following the convention, polygon PP is simple, if no two edges have any points in common, with the obvious exception of two consecutive segments having one common point.
The sum of m+nm+n from all test cases does not exceed 2⋅1062⋅106.
Output
For each test case, output the answer modulo 109+7109+7, that is, if the answer is PQPQ, you should output P⋅Q−1P⋅Q−1 modulo 109+7109+7, where Q−1Q−1 denotes the multiplicative inverse of QQ modulo 109+7109+7.
Sample Input复制
1
4
10 0
0 10
-10 0
0 -10
3
5 0
-15 -10
-15 10
Sample Output复制
666667713
提示
The intersection of the sample input is 3125/3. Prisms before intersection:
The intersection part looks like this:
The input size is quite large. Please mind the efficiency of your input buffer.
推荐代码 查看3037 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 |
赛题来源/所属竞赛 2019 Multi-University Training Contest 7 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|