CF1548D1.Gregor and the Odd Cows (Easy)

提高+/省选-

通过率:0%

时间限制:6.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

This is the easy version of the problem. The only difference from the hard version is that in this version all coordinates are even.

There are nn fence-posts at distinct coordinates on a plane. It is guaranteed that no three fence posts lie on the same line.

There are an infinite number of cows on the plane, one at every point with integer coordinates.

Gregor is a member of the Illuminati, and wants to build a triangular fence, connecting 33 distinct existing fence posts. A cow strictly inside the fence is said to be enclosed. If there are an odd number of enclosed cows and the area of the fence is an integer, the fence is said to be interesting.

Find the number of interesting fences.

这是该问题的简单版本。与困难版本的唯一区别在于:在此版本中,所有坐标均为偶数。

平面上有 nn 根互不重合的栅栏桩,其坐标互不相同。保证不存在三点共线的情况。

平面上有无穷多头牛,每头牛位于一个整数坐标点上(即所有形如 (x,y)(x, y) 的点,其中 x,yx, y 均为整数)。

Gregor 是光明会成员,他希望用三根不同的现有栅栏桩构成一个三角形围栏。严格位于该围栏内部的牛被称为被围住的牛。若被围住的牛的数量为奇数,且该围栏的面积为整数,则称该围栏是有趣的。

请计算有趣的围栏的数量。

输入格式

The first line contains the integer nn (3≤n≤60003 \le n \le 6000), the number of fence posts which Gregor can choose to form the vertices of a fence.

Each of the next nn line contains two integers xx and yy (0≤x,y≤1070 \le x,y \le 10^7, xx and yy are even), where (x,y)(x,y) is the coordinate of a fence post. All fence posts lie at distinct coordinates. No three fence posts are on the same line.

第一行包含一个整数 nn(3≤n≤60003 \le n \le 6000),表示 Gregor 可用于构成围栏顶点的围栏桩数量。

接下来的 nn 行,每行包含两个整数 xx 和 yy(0≤x,y≤1070 \le x,y \le 10^7,且 xx 和 yy 均为偶数),其中 (x,y)(x,y) 是一个围栏桩的坐标。所有围栏桩的坐标互不相同,且任意三个围栏桩均不共线。

输出格式

Print a single integer, the number of interesting fences. Two fences are considered different if they are constructed with a different set of three fence posts.

输出一个整数,表示有趣的围栏的数量。如果两个围栏所使用的三根围栏桩集合不同,则认为它们是不同的围栏。

输入输出样例

  • 输入#1

    3
    0 0
    2 0
    0 4

    输出#1

    1
  • 输入#2

    5
    0 0
    2 16
    30 14
    4 6
    2 10

    输出#2

    3

说明/提示

In the first example, there is only 11 fence. That fence is interesting since its area is 44 and there is 11 enclosed cow, marked in red.

In the second example, there are 33 interesting fences.

  • (0,0)(0,0) — (30,14)(30,14) — (2,10)(2,10)
  • (2,16)(2,16) — (30,14)(30,14) — (2,10)(2,10)
  • (30,14)(30,14) — (4,6)(4,6) — (2,10)(2,10)

在第一个例子中,只有一道围栏。这道围栏是“有趣的”,因为其面积为 44,且围住了 11 头奶牛(用红色标出)。

在第二个例子中,共有 33 道“有趣的”围栏:

  • (0,0)(0,0) — (30,14)(30,14) — (2,10)(2,10)
  • (2,16)(2,16) — (30,14)(30,14) — (2,10)(2,10)
  • (30,14)(30,14) — (4,6)(4,6) — (2,10)(2,10)

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

首页