P3021 [USACO11MAR]牛桥战役Bovine Bridge Battle

    • 17通过
    • 49提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2011 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

    给定N(4 <= N <= 1,000)个整点的坐标 (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000,X_i,Y_i∈Z),求card{{(X_a,Y_a),(X_b,Y_b),(X_c,Y_c),(X_d,Y_d)}|四点呈中心对称}

    题目描述

    Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting in the main pasture with cow i at point with integer coordinates (X_i, Y_i) (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000).

    The cows wish to form into groups of four in order to play Bridge, their new favorite card game. Each group must satisfy an important constraint: four cows are allowed to team up if and only if there exists some point X somewhere in the plane (and not coincident with any of the four points of the potential group of four) such that rotating any of the group's cows 180 degrees about that point X gives the position of some other cow in the group.

    Please help the cows determine the number of sets of four cows that can form a Bridge group.

    By way of example, suppose eight cows are standing at eight points:

    | f*

    |             a = (-3, 1)    e = (-1, 1) 
    b*     |             b = (-2, 2)    f = ( 0, 3) 
    a      e  |             c = (-3, 0)    g = ( 2, 0) 
    *     *  |             d = (-2, 0)    h = ( 3, 0) 

    c d | g h ---------*--*-----+-----*--*---------

    | Then the three legal sets of four cows are {a, b, e, d} (they rotate around point (-2, 1)), {b, c, e, f} (around the point (-1.5, 1.5)), and {c, d, g, h} (around (0,0)).

    The supplied locations of the cows given are all distinct, although they are supplied in no particular order. Furthermore, the answer will fit into a signed 32-bit integer.

    输入输出格式

    输入格式:

    * Line 1: A single integer: N

    * Lines 2..N+1: Line i+1 contains two space-separated integers: X_i and Y_i

    输出格式:

    * Line 1: A single integer that is the number of sets of 4 cows that form valid groups for bridge.

    输入输出样例

    输入样例#1: 复制
    8 
    -3 0 
    -2 0 
    -1 1 
    0 3 
    2 0 
    -3 1 
    3 0 
    -2 2 
    
    输出样例#1: 复制
    3 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。