CF1146H.Satanic Panic

省选/NOI-

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a set of nn points in a 2D plane. No three points are collinear.

A pentagram is a set of 55 points A,B,C,D,EA,B,C,D,E that can be arranged as follows. Note the length of the line segments don't matter, only that those particular intersections exist.

Count the number of ways to choose 55 points from the given set that form a pentagram.

给你平面上的 nn 个点,其中任意三点不共线。

五角星(pentagram)是指一组由 55 个点 A,B,C,D,EA,B,C,D,E 构成的集合,这些点可以按如下方式排列:

注意:线段的长度无关紧要,关键在于图中所示的特定交点必须存在。

请计算从给定点集中选出 55 个点能构成五角星的方案数。

输入格式

The first line contains an integer nn (5≤n≤3005 \leq n \leq 300) — the number of points.

Each of the next nn lines contains two integers xi,yix_i, y_i (−106≤xi,yi≤106-10^6 \leq x_i,y_i \leq 10^6) — the coordinates of the ii-th point. It is guaranteed that no three points are collinear.

第一行包含一个整数 nn(5≤n≤3005 \leq n \leq 300)—— 点的数量。

接下来的 nn 行中,每行包含两个整数 xi,yix_i, y_i(−106≤xi,yi≤106-10^6 \leq x_i,y_i \leq 10^6)—— 第 ii 个点的坐标。保证任意三个点不共线。

输出格式

Print a single integer, the number of sets of 55 points that form a pentagram.

输出一个整数,表示能构成五角星的 5 个点的集合的数量。

输入输出样例

  • 输入#1

    5
    0 0
    0 2
    2 0
    2 2
    1 3

    输出#1

    1
  • 输入#2

    5
    0 0
    4 0
    0 4
    4 4
    2 3

    输出#2

    0
  • 输入#3

    10
    841746 527518
    595261 331297
    -946901 129987
    670374 -140388
    -684770 309555
    -302589 415564
    -387435 613331
    -624940 -95922
    945847 -199224
    24636 -565799

    输出#3

    85

说明/提示

A picture of the first sample: A picture of the second sample: A picture of the third sample:

第一个样例的图片:
第二个样例的图片:
第三个样例的图片:

输入解题思路,AI测评打分。不知道怎么写?

首页