题解：SP34007 ADAM1 - Adrita and Marbles

· · 题解

题目大意

在二维平面内，给出一个圆的方程和若干个点，求出在圆内或圆上的点的数量。

解题思路

大部分人好像都是用的小数，可是为什么不能用整数呢？

这里根据式子 x^2+y^2-px-qy+z=0 转化一下。

根据《高中数学选择性必修一》相关内容，方程 x^2 +y^2+Dx+Ey+F=0 可以等效于：

(x+\frac{D}2)^2+(y+\frac{E}2)^2=\frac{D^2+E^2-4F}{4}

所以原方程可以变成：

(x-\frac{p}2)^2+(y-\frac{q}2)^2=\frac{p^2+q^2-4z}{4}

这个方程可以表示一个圆心在点 ( \frac{p}{2},\frac{q}{2}) 上的半径为 \sqrt{\frac{p^2+q^2-4z}{4}} 的圆。
点满足条件需要点与圆心的距离小于等于半径，也就是满足：

\sqrt{(x-\frac{p}{2})^2+(y-\frac{q}{2})^2}\le\sqrt{\frac{p^2+q^2-4z}{4}}

等效于满足：

(x-\frac{p}{2})^2+(y-\frac{q}{2})^2\le\frac{p^2+q^2-4z}{4}

同乘 4：

(2x-p)^2+(2y-q)^2 \le p^2+q^2-4z

这样就绝对不会有浮点误差了。
（其实就是 x^2+y^2-px-qy+z \le 0，不过书上好像都没提）

AC Code

#include<bits/stdc++.h>
#define code using
#define by namespace
#define zwz std
code by zwz;
#define ll long long
void solve() {
    ll n;
    ll p,q,z;
    ll x,y;
    ll ans=0;
    cin>>p>>q>>z>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        if(pow(2*x-p,2)+pow(2*y-q,2)<=p*p+q*q-4*z)ans++;
    }
    cout<<ans<<"\n";
}
int main() {
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}