uvalive 7675 | 2016 北京 regional onsite H - A New Ground Heating Device （二分+多个圆面积并）
题意：
在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。
思路：
训练的时候一眼二分，但是求圆并的时候gg了。。毫无思路。
搞定了多个圆面积并。。这题就很easy了。。
需要注意，每次二分的时候，记得初始化圆的d…
1/* ***********************************************
2Author :111qqz
3File Name :H.cpp
4************************************************ */
5
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define PB push_back
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27typedef long long LL;
28typedef unsigned long long ULL;
29typedef vector <int> VI;
30const int INF = 0x3f3f3f3f;
31const double eps = 1e-6;
32const int MAXN = 1E3+7;
33const double PI = acos(-1.0);
34#define sqr(x) ((x)*(x))
35const int N = 1010;
36double area[N];
37int n,k;
38double Z[N];
39double W,S;
40
41
42int dblcmp(double d){ return d<-eps?-1:d>eps;}
43struct point
44{
45 double x,y;
46 double ang;
47 int d;
48 point(){}
49 point(double x,double y):x(x),y(y){}
50 point(double _x,double _y,double _ang,int _d)
51 {
52 x = _x;
53 y = _y;
54 ang = _ang;
55 d = _d;
56 }
57 void input(){scanf("%lf%lf",&x,&y);}
58 double angle(){ return atan2(y,x);}
59 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
60 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
61 point operator * (double t)const{ return point(t*x,t*y);}
62 point operator / (double t)const{ return point(x/t,y/t);}
63 double length() const { return sqrt(x*x+y*y);};
64 double length2() const { return x*x + y*y;}
65 point unit()const { double l = length();return point(x/l,y/l); }
66}tp[N*2];
67double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
68double dist(const point p1,point p2) { return (p1-p2).length();}
69struct circle
70{
71 point c;
72 double r;
73 double Z;
74 int d;
75 void pr()
76 {
77 printf(" (%.3f,%.3f) r=%.3f\n",c.x,c.y,r);
78 }
79 void input()
80 {
81 c.input();
82 scanf("%lf",&r);
83 d = 1;
84 }
85 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
86 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
87} cir[N];// tp[N * 2];
88
89double dis(point a, point b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
90int CirCrossCir(circle cir1,circle cir2, point &p1, point &p2)
91{
92 point m = cir2.c-cir1.c;
93 point s = cir2.c+cir1.c;
94 point m2 = point(sqr(m.x),sqr(m.y));
95 double dis2 = m2.x + m2.y, d = -(dis2 - sqr(cir1.r - cir2.r)) * (dis2 - sqr(cir1.r + cir2.r));
96 if (d + eps < 0) return 0;
97 if (d < eps) d = 0;
98 else d = sqrt(d);
99 double x = m.x * ((cir1.r + cir2.r) * (cir1.r - cir2.r) + m.x * s.x) + s.x * m2.y;
100 double y = m.y * ((cir1.r+ cir2.r) * (cir1.r - cir2.r) + m.y * s.y) + s.y * m2.x;
101 point dp = m*d;
102 dis2 *= 2;
103 p1 = point (x-dp.y,y+dp.x)/dis2;
104 p2 = point (x+dp.y,y-dp.x)/dis2;
105 if (d > eps) return 2;
106 else return 1;
107}
108bool circmp(const circle& u, const circle& v)
109{
110 return dblcmp(u.r - v.r) < 0;
111}
112bool cmp(const point& u, const point& v)
113{
114 if (dblcmp(u.ang - v.ang)) return u.ang < v.ang;
115 return u.d > v.d;
116}
117
118double calc(circle cir, point p1, point p2)
119{
120 double ans = (p2.ang - p1.ang) * sqr(cir.r)
121 - cross ( (p1-cir.c),(p2-cir.c)) + cross( p1,p2);
122 return ans *0.5;
123}
124void CirUnion(circle cir[], int n)
125{
126 circle cir1, cir2;
127 point p1,p2;
128 sort(cir, cir + n, circmp);
129 for (int i = 0; i < n; ++i)
130 for (int j = i + 1; j < n; ++j)
131 if (cir[j].contain(cir[i]))
132 cir[i].d++;
133 for (int i = 0; i < n; ++i)
134 {
135 int tn = 0, cnt = 0;
136 for (int j = 0; j < n; ++j)
137 {
138 if (i == j) continue;
139 if (CirCrossCir(cir[i],cir[j],p2, p1) < 2) continue;
140 p1.ang = (p1-cir[i].c).angle();
141 p2.ang = (p2-cir[i].c).angle();
142 p1.d = 1;
143 tp[tn++] = p1;
144 p2.d = -1;
145 tp[tn++] = p2;
146 if (dblcmp(p1.ang - p2.ang) > 0) cnt++;
147 }
148 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, PI, -cnt);
149 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, -PI, cnt);
150 sort(tp, tp + tn, cmp);
151 int p, s = cir[i].d + tp[0].d;
152 for (int j = 1; j < tn; ++j)
153 {
154 p = s;
155 s += tp[j].d;
156 area[p] += calc(cir[i], tp[j - 1], tp[j]);
157 }
158 }
159}
160bool check( double h)
161{
162 // cout<<"h:"<<h<<" ";
163
164 for ( int i = 0 ; i < n ; i++)
165 {
166 double l = sqrt(cir[i].c.length2() + h*h);
167 double r = W/(l*cir[i].Z);
168 cir[i].r = r;
169 cir[i].d = 1; //多次，是累加值，记得每次二分都要初始化。
170 //cir[i].pr();
171 }
172
173 memset(area, 0, sizeof(area));
174 ms(tp,0);
175 CirUnion(cir, n);
176 //去掉重复计算的
177 for (int i = 1; i <= n; ++i)
178 {
179 area[i] -= area[i + 1];
180 }
181 //area[i]为重叠了i次的面积
182 double sum=0;
183 for ( int i = k ; i <= n ; i++) sum = sum + area[i];
184 //sum = fabs(sum);
185 return dblcmp(sum-S)>0;
186 //tot 为总面积
187 //double tot = 0;
188 //for(int i=1; i<=n; i++) tot += area[i];
189 //printf("%f\n", tot);
190}
191
192bool ok;
193double bin()
194{
195 double l = 0;
196 double r = 10000;
197 while (dblcmp(l-r)<0)
198 {
199 double mid = (l+r)*0.5;
200 //printf("l: %.4f r:%.4f mid:%.4f \n",l,r,mid);
201 if (check(mid)) l = mid,ok = true;
202 else r = mid;
203 }
204 return l;
205}
206int main()
207{
208 // freopen("./in.txt", "r", stdin);
209 int T;
210 cin>>T;
211 while (T--)
212 {
213 ok = false;
214 cin>>n>>W>>k>>S;
215 for ( int i = 0 ; i < n ; i++)
216 {
217 cir[i].c.input();
218 scanf("%lf",&cir[i].Z);
219 }
220 double ans =bin();
221 if (!ok) puts("No solution!");
222 else
223 {
224 if (dblcmp(ans-500)>0) puts("Oops!");
225 else printf("%.4f\n",ans);
226 }
227 }
228
229
230
231
232 return 0;
233}