P1715 [USACO16DEC]Lots of Triangles好多三角形

    • 39通过
    • 102提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2016 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John is thinking of selling some of his land to earn a bit of extra income. His property contains $N$ trees ($3 \leq N \leq 300$), each described by a point in the 2D plane, no three of which are collinear. FJ is thinking about selling triangular lots of land defined by having trees at their vertices; there are of course $L = \binom{N}{3}$ such lots he can consider, based on all possible triples of trees on his property.

    农民约翰希望通过卖出他拥有的一部分土地来增加收入。他在这片土地上种了$N$棵树($3\le N\le 300$),每棵树都可以用一个二维网格图上的一个坐标来表示,没有三棵树是共线的。约翰想以3棵树做顶点围成三角形来分割地,以确定地的大小和形状,基于约翰所有树可能组成的三树组合,当然有$L = \binom{N}{3}$种可能考虑分割贩卖的土地切块。

    A triangular lot has value $v$ if it contains exactly $v$ trees in its interior (the trees on the corners do not count, and note that there are no trees on the boundaries since no three trees are collinear). For every $v = 0 \ldots N-3$, please help FJ determine how many of his $L$ potential lots have value $v$.

    一块分出的三角形土地有价值$v$,$v$的大小决定于土地上树的数量,树的数量=土地价值=v (顶点上的树不算,网格图边界不种树)。当$v=0,1...N-3$时,请帮约翰求出有多少三角形地$L$拥有价值$v$。

    输入输出格式

    输入格式:

    The first line of input contains $N$.

    The following $N$ lines contain the $x$ and $y$ coordinates of a single tree; these are both integers in the range $0 \ldots 1,000,000$.

    输入的第一行为树的棵数$N$。

    接下来的$N$行分别为不同树在二维网格图上的坐标;它们都是介于$0$和$1000000$之间的的整数;行和列数间用空格隔开。

    输出格式:

    Output $N-2$ lines, where output line $i$ contains a count of the number of lots having value $i-1$.

    输出$N-2$行,其中第$i$行是价值$v$等于$i-1$的土地块数量。

    输入输出样例

    输入样例#1: 复制
    7
    3 6
    17 15
    13 15
    6 12
    9 1
    2 7
    10 19
    输出样例#1: 复制
    28
    6
    1
    0
    0

    说明

    感谢@Aaronlxz提供翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。