F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4357. -- Point

4357: Point

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 15  Solved: 2
[Submit][Status][Discuss]

Description

给出平面上n个点,保证没有两点重合或者三点共线。现在另外给出两个点P,Q,请求出有多少个点集的凸包包含P,Q(在边界上也算做包含)。为了简化,我们认为两个点的的凸包为两点之间的线段,此时只需要P,Q均在线段上即可。
答案模10^9+7。

Input

第一行一个整数n,N<=3000
接下来n行,每行两个整数x,y(x,y< = 10 ^ 9,描述一个点(x,y)。
接下来两行,每行两个整数,分别描述P,Q。

Output

一行一个整数,描述答案。

Sample Input

4
1 0
-1 0
0 1
0 -1
0 0
0 -1

Sample Output

5

HINT

 TCO2012 3B PQHulls

Source

[Submit][Status][Discuss]

HOME Back