问题 D: 飞艇航拍

问题 D: 飞艇航拍

时间限制: 1 Sec  内存限制: 128 MB
提交: 79  解决: 3
[状态] [讨论版] [提交] [命题人:]
题目描述

用飞艇进行空中拍照成本低,安全系数高,稳定性强,升空时间长,高度可以调节,准确度高。可用于影视、节目录制、企业资料和品牌推广、投资考察、城市规划与发展、新闻采集与事件报道、大型活动与赛事等领域。

现在我们有一个飞艇,想要对我们的学校进行拍摄,假设,我们的学校是一个多边形,他用相邻的顶点集合表示(每两个相邻的点,表示多边形的一条边,起点和终点是最后一条边)。我们让飞艇只进行简单的直线飞行。为了便于处理,我们引入直角坐标系,飞艇飞行的路线垂直于X坐标轴。现在我们想知道,飞艇在这条直线上,能拍到学校的y方向的长度是多少。假设摄像机拍摄的宽度非常小。

如图:a中拍到的长度就是多边形截取的长度,而b中长度是在多边形内的两线段的和。

输入

先给出测试数据组数TT<=20

对于每组测试数据

第一行输入多变形顶点个数N(1 <= N <= 50)

接下来N行,每行2个整数x(0<=x<=100)y(0<=y<=100)代表多边形的顶点坐标

最后是一个整数X(0<=X<=100),代表飞艇飞行的路线

输出

对于每组测试数据,求出飞艇拍下的学校y方向的长度,输出总长度的整数部分。每组输出各占一行。(注意:墙壁不算入长度)

样例输入 Copy
2
7
0 1
2 0
4 1
2 2
4 3
2 4
0 3
1
7
0 1
2 0
4 1
2 2
4 3
2 4
0 3
3
样例输出 Copy
3
2