8357: BZOJ4357:Point
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给出平面上n个点,保证没有两点重合或者三点共线。现在另外给出两个点P,Q,请求出有多少个点集的凸包包含P,Q(在边界上也算做包含)。为了简化,我们认为两个点的的凸包为两点之间的线段,此时只需要P,Q均在线段上即可。 答案模10^9+7。
输入格式
第一行一个整数n,N<=3000 接下来n行,每行两个整数x,y(x,y< = 10 ^ 9,描述一个点(x,y)。 接下来两行,每行两个整数,分别描述P,Q。
输出格式
一行一个整数,描述答案。
样例输入
4 1 0 -1 0 0 1 0 -1 0 0 0 -1
样例输出
5
提示
TCO2012 3B PQHulls
题目来源
没有写明来源