CF1284E.New Year and Castle Construction
省选/NOI-
通过率:0%
时间限制:3.00s
内存限制:1024MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Kiwon's favorite video game is now holding a new year event to motivate the users! The game is about building and defending a castle, which led Kiwon to think about the following puzzle.
In a 2-dimension plane, you have a set s=(x1,y1),(x2,y2),…,(xn,yn) consisting of n distinct points. In the set s, no three distinct points lie on a single line. For a point p∈s, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with 4 vertices) that strictly encloses the point p (i.e. the point p is strictly inside a quadrilateral).
Kiwon is interested in the number of 4-point subsets of s that can be used to build a castle protecting p. Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.
Let f(p) be the number of 4-point subsets that can enclose the point p. Please compute the sum of f(p) for all points p∈s.
Kiwon 最喜欢的视频游戏目前正在举办新年活动,以激励玩家!该游戏的主题是建造和保卫城堡,这促使 Kiwon 思考了如下谜题。
在二维平面上,给定一个由 n 个互异点组成的集合 s=(x1,y1),(x2,y2),…,(xn,yn)。在集合 s 中,任意三个互异点均不共线。对于点 p∈s,我们可以通过建造一座城堡来保护该点。所谓城堡,是指一个简单四边形(即具有 4 个顶点的多边形),且该四边形严格包含点 p(即点 p 严格位于该四边形内部)。
Kiwon 关心的是:集合 s 中有多少个由 4 个点构成的子集,可以用来建造一座能保护点 p 的城堡。注意:若某个四点子集可通过多种连接方式围成包含 p 的四边形,则该子集仅计一次。
令 f(p) 表示能围住点 p 的四点子集的个数。请计算对所有点 p∈s 的 f(p) 之和。
输入格式
The first line contains a single integer n (5≤n≤2500).
In the next n lines, two integers xi and yi (−109≤xi,yi≤109) denoting the position of points are given.
It is guaranteed that all points are distinct, and there are no three collinear points.
第一行包含一个整数 n(5≤n≤2500)。
接下来的 n 行中,每行给出两个整数 xi 和 yi(−109≤xi,yi≤109),表示各点的坐标。
保证所有点互不相同,且不存在三点共线的情况。
输出格式
Print the sum of f(p) for all points p∈s.
打印所有点 p∈s 对应的 f(p) 的总和。
输入输出样例
输入#1
5 -1 0 1 0 -10 -1 10 -1 0 3
输出#1
2
输入#2
8 0 1 1 2 2 2 1 3 0 -1 -1 -2 -2 -2 -1 -3
输出#2
40
输入#3
10 588634631 265299215 -257682751 342279997 527377039 82412729 145077145 702473706 276067232 912883502 822614418 -514698233 280281434 -41461635 65985059 -827653144 188538640 592896147 -857422304 -529223472
输出#3
213
输入解题思路,AI测评打分。不知道怎么写?