题意:给你n个圆,每个圆有一个权值,你可以选择一个点,可以获得覆盖这个点的圆中,权值最大的m个的权值,问最多权值是多少
题解:好像是叙利亚的题....我们画画图就知道,我们要找的就是圆与圆交的那部分里面的点,我们再仔细看看,
2个圆的交点一定在啊！
别急啊,两个圆包含了,都是交点,取哪呢？当然小圆圆心就够了啊(圆又不多,写的时候直接把所有的圆心都丢进去了)
然后枚举判断每个点有没有被在m个圆中就行了,这里维护最大的m个,用个堆就好了
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps = 1e-;
int dcmp(ld x)
{
if(fabs(x) < eps) return ;
return x < ? - : ;
}
ld sqr(ld x) { return x * x; }
struct Point
{
ld x, y;
Point(ld x = , ld y = ):x(x), y(y) {}
};
Point operator - (const Point& A, const Point& B)
{
return Point(A.x - B.x, A.y - B.y);
}
bool operator == (const Point& A, const Point& B)
{
return dcmp(A.x - B.x) == && dcmp(A.y - B.x) == ;
}
ld Dot(const Point& A, const Point& B)
{
return A.x * B.x + A.y * B.y;
}
ld dis(Point a,Point b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
ld Length(const Point& A) { return sqrt(Dot(A, A)); }
ld angle(Point v) { return atan2(v.y, v.x); }
struct Circle
{
Point c;
ld r,v;
Circle() {}
Circle(Point c, ld r):c(c), r(r) {}
inline Point point(double a)
{
return Point(c.x+cos(a)*r, c.y+sin(a)*r);
}
}a[];
int getCircleCircleIntersection(Circle C1, Circle C2,Point &t1,Point &t2)
{
ld d = Length(C1.c - C2.c);
if(dcmp(d) == )
{
if(dcmp(C1.r - C2.r) == ) return -;
return ;
}
if(dcmp(C1.r + C2.r - d) < ) return ;
if(dcmp(fabs(C1.r-C2.r) - d) > ) return ;
ld a = angle(C2.c - C1.c);
ld da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (*C1.r*d));
Point p1 = C1.point(a-da), p2 = C1.point(a+da);
t1=p1;
if(p1 == p2) return ;
t2=p2;
return ;
}
Point jd[];
ld ans,sum;
int n,m,T,tot;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
scanf("%d",&T);
while (T--)
{
tot=;
ans=;
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%Lf%Lf%Lf%Lf",&a[i].c.x,&a[i].c.y,&a[i].r,&a[i].v);
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++)
{
Point t1,t2;
int why=getCircleCircleIntersection(a[i],a[j],t1,t2);
if (why==)
{
tot++;
jd[tot]=t1;
}else
if (why==)
{
tot++;jd[tot]=t1;
tot++;jd[tot]=t2;
}
}
for (int i=;i<=n;i++)
{
tot++;
jd[tot]=a[i].c;
}
for (int i=;i<=tot;i++)
{
for (int j=;j<=n;j++)
if (dcmp(dis(jd[i],a[j].c)-a[j].r)<=)
{
q.push(a[j].v);
if ((int)q.size()>m) q.pop();
}
sum=;
while (!q.empty()) sum+=q.top(),q.pop();
ans=max(ans,sum);
}
printf("%.Lf\n",ans);
}
}