星球大战

链接：https://ac.nowcoder.com/acm/contest/321/F

题目描述

FF上次在大家的帮助下算出了呼唤到了足够多的人数再一次阻拦了丧心病狂的NE。然后机智的FF为了继续摸鱼决定搬离地球到达BD星来防止NE再次gank。

可是FF错误估计了NE丧心病狂的程度。NE居然拿出了终极武器“朗基努斯之枪”。用“朗基努斯之枪”可以发出激光攻击BD星。NE决定直接摧毁BD星让FF无处可逃。这个时候BD哥站了出来。

BD哥：“正好试试我新研发的激光抵御装置1.0版本-反射护罩！”

FF:“难道是传说中的禁卡，可以破坏敌人所有的攻击表示的怪兽吗！”

BD哥：“FF你在胡说什么。”(说着FF遭到了BD哥的敲打，生命-1。

BD哥详细的给FF解释了一下这个装置的效果：

________________________________________

这个装置是一个球体，任何穿过这个球体的激光都会遭到削弱。

为了简化题目，我们将其看做二维平面：

攻击点A即NE所在位置，我们保证反射护罩的圆心的y坐标与攻击点A的y坐标相同。

令y轴为FF所在的BD星的地面。

每次攻击发射一条激光，有一个初始能量值Ci。

若激光穿过反射护罩，那么它将与反射护罩产生2个交点B,C（更接近A的交点为B,远者为C，保证B、C不重合）。

记AB长度为a,BC的长度为b,那么这条激光的能量值就会减少a2+ab。

削减后能量值如果小于0则光线消失。(即不会有能量值为负的光线到达BD星)；

FF想知道,最后BD星会遭受的总共多少能量值的激光攻击。

输入描述:

第一行包含一个正整数T(1<=T<=300)。
接下来有T组数据。
每组数据的第一行包含5个整数，xa,ya,xr,r,n(1<=xa,ya,xr,r<=15000；1<=n<=1000)，分别代表A的x坐标，A的y的坐标，反射装置的圆心的x坐标，反射装置的半径，与攻击次数。
我们保证攻击点A在圆外并且xa>xr;
接下来n行。每行包含2个整数 y0,Ci(0<=y0<=15000,0<=Ci<109),代表A发出的攻击所想要攻击到的目标点（0，y0）和这条激光的能量值Ci。

输出描述:

对于每组数据,输出一行,

包含一个整数,表达受到的所有攻击的能量值的和。

示例1

输入

复制

1
3 1 1 1 5
0 2
2 2
1 4
4 10
5 10

输出

复制

21

首先，说下利用三角形相似的解法。

话不多说，直接上图。

#include<bits/stdc++.h>
#define    ll long long

int T;
int xa,ya,xr,r,n;
int main()
{
    int T;
    scanf(\"%d\",&T);
    while(T--)
    {
        scanf(\"%d%d%d%d%d\",&xa,&ya,&xr,&r,&n);
        double num_puts=0;
        int y;
        double energy;
        double l1,l2,l3;
        double a,b;
        while(n--)
        {
          scanf(\"%d%lf\",&y,&energy);
          l1=(xa*xa-xa*xr)*1.0/sqrt(xa*xa+(y-ya)*(y-ya));
          l2=(xa-xr)*abs(y-ya)*1.0/sqrt(xa*xa+(y-ya)*(y-ya));
          if(l2>r)
          {
              num_puts+=energy;
              continue;
          }
            l3=sqrt(r*r-l2*l2);
          a=l1-l3;
          b=2*l3;
          double c=energy-a*a-a*b;
          if(c<0) c=0;
          num_puts=num_puts+c;
        }
        printf(\"%lld\\n\",(ll)num_puts);
    }
    return 0;
}