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;  
}