uvalive 7675 | 2016 北京 regional onsite H - A New Ground Heating Device （二分+多个圆面积并）
题意：
在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。
思路：
训练的时候一眼二分，但是求圆并的时候gg了。。毫无思路。
搞定了多个圆面积并。。这题就很easy了。。
需要注意，每次二分的时候，记得初始化圆的d...
/* ***********************************************
Author :111qqz
File Name :H.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19#define pi pair < int ,int >
20#define MP make_pair
21using namespace std;
22typedef long long LL;
23typedef unsigned long long ULL;
24typedef vector <int> VI;
25const int INF = 0x3f3f3f3f;
26const double eps = 1e-6;
27const int MAXN = 1E3+7;
28const double PI = acos(-1.0);
29#define sqr(x) ((x)*(x))
30const int N = 1010;
31double area[N];
32int n,k;
33double Z[N];
34double W,S;
1int dblcmp(double d){ return d<-eps?-1:d>eps;}
2struct point
3{
4 double x,y;
5 double ang;
6 int d;
7 point(){}
8 point(double x,double y):x(x),y(y){}
9 point(double _x,double _y,double _ang,int _d)
10 {
11 x = _x;
12 y = _y;
13 ang = _ang;
14 d = _d;
15 }
16 void input(){scanf("%lf%lf",&x,&y);}
17 double angle(){ return atan2(y,x);}
18 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
19 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
20 point operator * (double t)const{ return point(t*x,t*y);}
21 point operator / (double t)const{ return point(x/t,y/t);}
22 double length() const { return sqrt(x*x+y*y);};
23 double length2() const { return x*x + y*y;}
24 point unit()const { double l = length();return point(x/l,y/l); }
25}tp[N*2];
26double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
27double dist(const point p1,point p2) { return (p1-p2).length();}
28struct circle
29{
30 point c;
31 double r;
32 double Z;
33 int d;
34 void pr()
35 {
36 printf(" (%.3f,%.3f) r=%.3f\n",c.x,c.y,r);
37 }
38 void input()
39 {
40 c.input();
41 scanf("%lf",&r);
42 d = 1;
43 }
44 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
45 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
46} cir[N];// tp[N * 2];
1double dis(point a, point b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
2int CirCrossCir(circle cir1,circle cir2, point &p1, point &p2)
3{
4 point m = cir2.c-cir1.c;
5 point s = cir2.c+cir1.c;
6 point m2 = point(sqr(m.x),sqr(m.y));
7 double dis2 = m2.x + m2.y, d = -(dis2 - sqr(cir1.r - cir2.r)) * (dis2 - sqr(cir1.r + cir2.r));
8 if (d + eps < 0) return 0;
9 if (d < eps) d = 0;
10 else d = sqrt(d);
11 double x = m.x * ((cir1.r + cir2.r) * (cir1.r - cir2.r) + m.x * s.x) + s.x * m2.y;
12 double y = m.y * ((cir1.r+ cir2.r) * (cir1.r - cir2.r) + m.y * s.y) + s.y * m2.x;
13 point dp = m*d;
14 dis2 *= 2;
15 p1 = point (x-dp.y,y+dp.x)/dis2;
16 p2 = point (x+dp.y,y-dp.x)/dis2;
17 if (d > eps) return 2;
18 else return 1;
19}
20bool circmp(const circle& u, const circle& v)
21{
22 return dblcmp(u.r - v.r) < 0;
23}
24bool cmp(const point& u, const point& v)
25{
26 if (dblcmp(u.ang - v.ang)) return u.ang < v.ang;
27 return u.d > v.d;
28}
1double calc(circle cir, point p1, point p2)
2{
3 double ans = (p2.ang - p1.ang) * sqr(cir.r)
4 - cross ( (p1-cir.c),(p2-cir.c)) + cross( p1,p2);
5 return ans *0.5;
6}
7void CirUnion(circle cir[], int n)
8{
9 circle cir1, cir2;
10 point p1,p2;
11 sort(cir, cir + n, circmp);
12 for (int i = 0; i < n; ++i)
13 for (int j = i + 1; j < n; ++j)
14 if (cir[j].contain(cir[i]))
15 cir[i].d++;
16 for (int i = 0; i < n; ++i)
17 {
18 int tn = 0, cnt = 0;
19 for (int j = 0; j < n; ++j)
20 {
21 if (i == j) continue;
22 if (CirCrossCir(cir[i],cir[j],p2, p1) < 2) continue;
23 p1.ang = (p1-cir[i].c).angle();
24 p2.ang = (p2-cir[i].c).angle();
25 p1.d = 1;
26 tp[tn++] = p1;
27 p2.d = -1;
28 tp[tn++] = p2;
29 if (dblcmp(p1.ang - p2.ang) > 0) cnt++;
30 }
31 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, PI, -cnt);
32 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, -PI, cnt);
33 sort(tp, tp + tn, cmp);
34 int p, s = cir[i].d + tp[0].d;
35 for (int j = 1; j < tn; ++j)
36 {
37 p = s;
38 s += tp[j].d;
39 area[p] += calc(cir[i], tp[j - 1], tp[j]);
40 }
41 }
42}
43bool check( double h)
44{
45 // cout<<"h:"<<h<<" ";
1 for ( int i = 0 ; i < n ; i++)
2 {
3 double l = sqrt(cir[i].c.length2() + h*h);
4 double r = W/(l*cir[i].Z);
5 cir[i].r = r;
6 cir[i].d = 1; //多次，是累加值，记得每次二分都要初始化。
7 //cir[i].pr();
8 }
1 memset(area, 0, sizeof(area));
2 ms(tp,0);
3 CirUnion(cir, n);
4 //去掉重复计算的
5 for (int i = 1; i <= n; ++i)
6 {
7 area[i] -= area[i + 1];
8 }
9 //area[i]为重叠了i次的面积
10 double sum=0;
11 for ( int i = k ; i <= n ; i++) sum = sum + area[i];
12 //sum = fabs(sum);
13 return dblcmp(sum-S)>0;
14 //tot 为总面积
15 //double tot = 0;
16 //for(int i=1; i<=n; i++) tot += area[i];
17 //printf("%f\n", tot);
18}
1bool ok;
2double bin()
3{
4 double l = 0;
5 double r = 10000;
6 while (dblcmp(l-r)<0)
7 {
8 double mid = (l+r)*0.5;
9 //printf("l: %.4f r:%.4f mid:%.4f \n",l,r,mid);
10 if (check(mid)) l = mid,ok = true;
11 else r = mid;
12 }
13 return l;
14}
15int main()
16{
17 // freopen("./in.txt", "r", stdin);
18 int T;
19 cin>>T;
20 while (T--)
21 {
22 ok = false;
23 cin>>n>>W>>k>>S;
24 for ( int i = 0 ; i < n ; i++)
25 {
26 cir[i].c.input();
27 scanf("%lf",&cir[i].Z);
28 }
29 double ans =bin();
30 if (!ok) puts("No solution!");
31 else
32 {
33 if (dblcmp(ans-500)>0) puts("Oops!");
34 else printf("%.4f\n",ans);
35 }
36 }
return 0;
}