bzoj

题目描述

 有一天,小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的值。


 

  • 题解

    • 题目中的"W"是左右对称的,并且由于左右两边都x轴严格所以互不影响
    • 那么对每个三号点统计出左"V"和右"V"相乘即可得到答案;
    • 下面的诉述均在三号点确定的情况下;
    • 考虑统计左"V",即满足条件①的对数:
    • $$①:x_{1} < x_{2} < x_{3},y_{2} < y_{1} < y_{3}$$
    • 采用容斥,首先按x坐标做扫描线,可以用两个树状数组统计出条件②:
    • $$②:x_{1} < x_{2} < x_{3},y_{2} < y_{1}且y_{2} < y_{3}$$
    • ②包含①,和①对比需要再统计条件③:
    • $$③:x_{1} < x_{2} < x_{3},y_{2} < y_{1} <= y_{3}$$
    • 统计在$x_{3}$严格左边,不严格的下边的点数$num$,C_{num}^{2} 可表示条件④:
      $$④:x_{1} <= x_{2} < x_{3},y_{1},y_{2}<= y_{3}$$
    • 用一个树状数组去掉$x$轴的等号进一步统计⑤:
    • $$⑤:x_{1} < x_{2} < x_{3},y_{1},y_{2} <= y_{3}$$
    • 同理用两个树状数组统计⑥:
    • $$⑥:x_{1} < x_{2} < x_{3},y_{1} <= y_{2} <= y_{3}$$
    • 用⑥减去⑤得到③,用②减去③得到①;
    • 建议画图思考,想清楚再写TAT.........
上一篇:(计算几何基础 叉积)nyoj68-三点顺序


下一篇:bzoj2441【中山市选】小W的问题