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)s = {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)} consisting of nn distinct points. In the set ss, no three distinct points lie on a single line. For a point p∈sp \in s, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with 44 vertices) that strictly encloses the point pp (i.e. the point pp is strictly inside a quadrilateral).

Kiwon is interested in the number of 44-point subsets of ss that can be used to build a castle protecting pp. 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)f(p) be the number of 44-point subsets that can enclose the point pp. Please compute the sum of f(p)f(p) for all points p∈sp \in s.

Kiwon 最喜欢的视频游戏目前正在举办新年活动,以激励玩家!该游戏的主题是建造和保卫城堡,这促使 Kiwon 思考了如下谜题。

在二维平面上,给定一个由 nn 个互异点组成的集合 s=(x1,y1),(x2,y2),…,(xn,yn)s = {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)}。在集合 ss 中,任意三个互异点均不共线。对于点 p∈sp \in s,我们可以通过建造一座城堡来保护该点。所谓城堡,是指一个简单四边形(即具有 4 个顶点的多边形),且该四边形严格包含点 pp(即点 pp 严格位于该四边形内部)。

Kiwon 关心的是:集合 ss 中有多少个由 4 个点构成的子集,可以用来建造一座能保护点 pp 的城堡。注意:若某个四点子集可通过多种连接方式围成包含 pp 的四边形,则该子集仅计一次。

令 f(p)f(p) 表示能围住点 pp 的四点子集的个数。请计算对所有点 p∈sp \in s 的 f(p)f(p) 之和。

输入格式

The first line contains a single integer nn (5≤n≤2 5005 \le n \le 2\,500).

In the next nn lines, two integers xix_i and yiy_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9) denoting the position of points are given.

It is guaranteed that all points are distinct, and there are no three collinear points.

第一行包含一个整数 nn(5≤n≤2 5005 \le n \le 2\,500)。

接下来的 nn 行中,每行给出两个整数 xix_i 和 yiy_i(−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9),表示各点的坐标。

保证所有点互不相同,且不存在三点共线的情况。

输出格式

Print the sum of f(p)f(p) for all points p∈sp \in s.

打印所有点 p∈sp \in s 对应的 f(p)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测评打分。不知道怎么写?

首页