bzoj#P2441. [中山市选2011]小W的问题
[中山市选2011]小W的问题
题目描述
小W的问题
【问题描述】
有一天,小 W 找了一个笛卡尔坐标系,并在上面选取了 N个整点。他发现通过这些整点能够画出很多个“ W ”出来。具体来说,对于五个 不同的点 ( x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5) ,如果满足:
- x1 < x2 < x3 < x4 < x5
- y1 > y3 > y2
- y5 > y3 > y4 则称它们构成一个“ W ”形。 现在,小 W 想统计“ W ”形的个数,也就是满足上面条件的五元点组个数。你能帮助他吗?
。
输入格式
** 第一行包含一个整数** N,表示点的个数。
下面N行每行两个整数,第i+1 行为 ( xi, yi) ,表示第 i个点的坐标。
输出格式
仅包含一行,为“ W ”形个数模 1 000 000 007 的值 。
6
1 10
2 1
3 5
4 6
5 1
6 10
3
提示
对于100%的数据满足N ≤ 200 000,0 ≤ xi ≤ 10^9,0 ≤ yi ≤ 10^9
题目来源
Day2