IT’S HIGH NOON!
Mccree’s ultimate skill has cooled down! He can aim at arbitrary direction and shoot all the enemies in front of him in a range of 180 degrees (A half plane, the border of which passes through Mccree. The enemies on the border will also be shot).
He can only aim for several seconds, so the range he can move in is a circle (He can aim on the border of the circle). The center of the circle is (0, 0) and the radius is . He wants to know how many enemies at most he can beat down in one shot.
Input There are multiple test cases. The first line of input is a integer (), indicating the number of test cases. For each test case:
The first line contains two integers () and (), indicating the number of enemies and the radius of the circle.
The following lines each contains two integers and (), indicating the coordinate of each enemy.
Output For each case output one line containing one integer, indicating the maximum number of enemies Mccree can shoot.
Sample Input 1 4 1 2 2 2 -2 -2 -2 -2 2 Sample Output 3 Hint A solution for the sample test case is shown as follows.
题意： 你可以在一个点进行攻击，攻击范围为这个点作直线后的半个平面。 点的范围为半径为R圆心(0,0)的圆。 求最多攻击到多少个点。
思路： 可以想到，你肯定是站在圆的边界上，然后对圆作切线进行攻击更优。
其他每个点对圆作切线，假设两个切点点极角为 L , R L,R L,R，则只要你位于圆边界上角度范围在L->R的点，都可以攻击到这个点。
这实际上等价于区间更新然后去最大值（只不过这个区间是环形的，注意当 L > R L>R L>R的时候，范围为 L − > 2 ∗ P I , 0 − > R L->2*PI, 0->R L−>2∗PI,0−>R）。用差分维护区间更新然后扫一遍就好了。
#include <algorithm> #include <iostream> #include <cassert> #include <cstdlib> #include <cstdio> #include <vector> #include <queue> #include <cmath> using namespace std; typedef long long ll; const int maxn = 1e5 + 7; const double eps = 1e-8; const double PI = acos(-1); int n,r; struct Point { double x,y; bool operator * (const Point&rhs) const { return x * rhs.y - y * rhs.x; } }a[maxn]; int sign(double x) { //判断正负 if(x > eps) return 1; if(x < -eps) return -1; return 0; } double getdis(Point a,Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double Mod(double rad) { if(rad < 0) rad += 2 * PI; if(rad > 2 * PI) rad -= 2 * PI; return rad; } int solve() { int ans = 0; Point O = {0.0,0.0}; vector<pair<double,int> >vec; int now = 0; for(int i = 1;i <= n;i++) { double dis = getdis(O,a[i]); if(dis <= r) { //在圆内或圆上 now++; } else { double rad = atan2(a[i].y,a[i].x); double w = acos(1.0 * r / dis); double L = rad + w, R = rad - w; L = Mod(L); R = Mod(R); if(L > R) { vec.push_back({0,1}); vec.push_back({R,-1}); vec.push_back({L,1}); } else { vec.push_back({L,1}); vec.push_back({R,-1}); } } } sort(vec.begin(),vec.end()); ans = now; for(int i = 0;i < vec.size();i++) { now += vec[i].second; ans = max(ans,now); } return ans; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&r); for(int i = 1;i <= n;i++) { scanf("%lf%lf",&a[i].x,&a[i].y); } printf("%d\n",solve()); } return 0; }