AT_arc082_c.[ARC082E] ConvexScore

NOI/NOI+/CTSC

通过率:0%

AC君温馨提醒

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

题目描述

给你 NN 个二维平面上的点 (xi,yi)(x_i,y_i),考虑 NN 个点的一个子集 SS,我们称它构成一个凸多边形,当且仅当存在一个面积为正数的凸多边形,其点集为 SS。这个多边形的所有内角都要严格小于 180°180\degree。

例如,在上图中,{A,C,E}\{A,C,E\} 和 {B,D,E}\{B,D,E\} 构成凸多边形,{A,C,D,E},A,B,C,E,{A,B,C},{D,E}\{A,C,D,E\},{A,B,C,E},\{A,B,C\},\{D,E\} 和 {}\{\} 则不构成。

对于一个点集 SS,令 nn 为 NN 个点中位于 SS 的凸包内(包括内部和边界)的点的个数。我们定义 SS 的分数为 2n−∣S∣2^{n-\vert S\vert}。

求这 NN 个点的构成凸多边形的子集 SS 的分数之和。

由于答案可以很大,你需要输出答案对 998244353998244353 取模后的值。

输入格式

第一行一个整数 N(1≤N≤200)N(1\le N\le 200)。

接下来 NN 行,每行两个整数 xi,yi(0≤xi,yi<104)x_i,y_i(0\le x_i,y_i<10^4),保证没有两个相同的点。

输出格式

输出一行一个整数,表示分数之和对 998244353998244353 取模后的值。

输入输出样例

  • 输入#1

    4
    0 0
    0 1
    1 0
    1 1

    输出#1

    5
  • 输入#2

    5
    0 0
    0 1
    0 2
    0 3
    1 1

    输出#2

    11
  • 输入#3

    1
    3141 2718

    输出#3

    0

说明/提示

样例 1 解释

我们有 55 个可以构成凸多边形的 SS,其中四个构成三角形,一个构成四边形。其中每一个的分数都是 20=12^0=1,所以答案是 55。

样例 2 解释

我们有三个 11 分的三角形 SS,两个 22 分的三角形 SS,一个 44 分的三角形 SS,所以答案是 1111。

样例 3 解释

没有构成凸多边形的 SS,所以答案是 00。

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

首页