/ Vijos / 题库 /

校园足迹

校园足迹

描述

和木姑娘在一起的校园时光总是甜蜜的。向那一排笔直站立的白桦树一一问声好,牵着手在广场上跳着格子舞,在国旗下看红旗飘扬,在老图书馆前嬉笑。

校园里几乎每一处角落,都有美好的记忆。这些记忆有的甜蜜幸福,有的青涩美好。

如果把n段记忆镶嵌在校园里,在平面上用n组坐标来表示,那么哪些才是甜蜜幸福的粉色回忆,哪些才是蓝色的青涩回忆呢?

只要尝试在平面上走出一条直线来,所有的记忆或者在直线的左侧或者在右侧,左侧望去的所有记忆是粉色的,右侧所有的记忆就是蓝色的,这就是一种分配了。但是要保证至少有一次回忆是粉色的,至少有一次回忆是蓝色的。

那么,这样的分配一共有多少种呢?

格式

输入格式

第一行一个整数n(1<=n<=300),表示有n段记忆。

之后n行,每行给出坐标(xi,yi),-10000<=xi,yi<=10000。

输出格式

输出一个整数,表示有多少种不同的分配方法。

样例1

样例输入1

4
0 0
1 0
1 1
0 1

样例输出1

12

限制

50%的数据,n<=10.
100%的数据,n<=300.

信息

ID
1920
难度
8
分类
组合数学 | 容斥原理 点击显示
标签
(无)
递交数
155
已通过
23
通过率
15%
上传者

相关