P3091 [USACO13NOV]视线Line of Sight

    • 12通过
    • 65提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2013 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

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

    题目描述

    Farmer John's N cows (1 <= N <= 50,000) are located at distinct points in his two-dimensional pasture. In the middle of the pasture is a large circular grain silo. Cows on opposite sides of the silo cannot see each-other, since the silo blocks their view. Please determine the number of pairs of cows that can see each-other via a direct line of sight.

    The grain silo is centered at the origin (0,0) and has radius R. No cow is located on or inside the circle corresponding to the silo, and no two cows lie on a tangent line to the silo. The value of R is in the range 1..1,000,000, and each cow lives at a point with integer coordinates in the range -1,000,000..+1,000,000.

    农民约翰的n头奶牛(1 < = n=50000)位于他的二维牧场的不同地点。在牧场的中部是一个大的圆形谷物筒仓。在筒仓对面的奶牛不能看到对方,因为筒仓挡住了他们的视线。请确定一对能直接通过视线看到的牛的数目。

    粮食筒仓的中心在原点(0,0),半径R没有牛位于或圈内相应的筒仓,没有两牛躺在切线的筒仓。r的值在1。1000000的范围内,而每一头奶牛的生命值都在整数坐标的范围内——1000000±1000000。

    Translated by @dijiuheng9

    输入输出格式

    输入格式:

    * Line 1: Two integers: N and R.

    * Lines 2..1+N: Each line contains two integers specifying the (x,y) coordinates of a cow.

    输出格式:

    * Line 1: The number of pairs of cows who can see each-other.

    输入输出样例

    输入样例#1: 复制
    4 5 
    0 10 
    0 -10 
    10 0 
    -10 0 
    
    输出样例#1: 复制
    4 
    

    说明

    There are 4 cows at positions (0,10), (0,-10), (10,0), and (-10,0). The silo is centered at (0,0) and has radius 5.

    All 6 pairs of cows can see each-other, except for the pairs situated on opposite sides of the silo: the cows at (-10,0) and (10,0) cannot see each-other, and the cows at (0,-10) and (0,10) cannot see each-other.

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