在Aalam-Aara(意为地球之光)小镇,以前没有犯罪,没有罪犯,但随着时间的推移,罪恶开始蔓延到曾经正义的人们的心中。在寻求解决问题的方法时,一些长老发现,只要让腐败的部分远离未腐败的部分,犯罪就可以制止。所以,他们试图建立一个大院来关押腐败分子。为了确保罪犯不会逃出大院,需要设立一个瞭望塔,以便监视他们。
由于Aalam-Aara的人民不是很富有,他们遇到了一位来自某个富裕城镇的商人,商人同意卖给他们一块土地,这块土地已经有直线围栏AB,沿着围栏设立了几个点,他们可以在那里搭建瞭望塔。你的任务是帮助他们找出栅栏上可以竖起塔的点的数量,以便从那里监视所有的罪犯。只可设置一座瞭望塔。如果从瞭望塔到犯罪分子的视线没有穿过犯罪分子和犯罪分子与塔楼之间的任何点的绘图边缘,即如下图 1 所示,从 B 点可以看到 X、Y、C 和 A 点,但从 E 点和 D 点看不到,则可以从瞭望塔看到该犯罪分子。
图1
图2
假设地块呈多边形,已设置坐标轴,使围栏AB与x轴平行,可设置瞭望塔的点为线上的整数点。例如,在给定的图2中,瞭望塔可以设置在AB上的五个整数点中的任意一个上,即(4, 8)、(5, 8)、(6, 8)、(7, 8)或(8, 8)。您可以假设没有三个连续点共线,并且除 A 和 B 之外的所有角点都位于栅栏 AB 的同一侧。给定的多边形不包含自相交。
输入
测试用例的第一行将包含顶点数 n (3 ≤ n ≤ 1000)。
接下来的 n 行将包含按多边形顺时针顺序排列的顶点坐标。第 i 行是整数 xi 和 yi (0 ≤ xi, yi ≤ 106),用空格分隔。
栅栏 AB 的端点是前两个点 (x1, y1) 和 (x2, y2)。
输出
输出由一行组成,其中包含可以设置瞭望塔的点数。
示例
输入 #1
5 4 8 8 8 9 4 4 0 0 4
输出 #1
5
输入 #2
5 4 8 5 8 5 4 7 4 2 2
输出 #2
0
注意
图 2 显示了第一个测试用例。从栅栏 AB 上的任意点都可以观看图中的所有点。因为AB有5个整数坐标,所以答案是5。
对于情况二,栅栏 CD 和 DE 不完全可见,因此答案为 0。