spoj CIRU – The area of the union of circles (多个圆面积并，模板题)

2017年10月11日 0 作者 CrazyKK

题目链接

题意：

多n个圆的面积并。

思路：

发现和求2个圆的完全不一样，具体请参考

SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）

圆的面积并 

格林公式在面积并问题中的应用

（用格林公式搞真是跪烂了。。。。

没有仔细看细节，当成板子好了(我最菜.jpg

将代码写成了自己熟悉的风格。

以及双倍经验题:SPOJ VCIRCLES

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N =1e3+7;
inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
struct point
{
    double x,y;
    point(){}
    point(double x,double y):x(x),y(y){}
    void input(){scanf("%lf%lf",&x,&y);}
    double angle(){ return atan2(y,x);}
    point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
    point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
    point operator * (double t)const{ return point(t*x,t*y);}
    point operator / (double t)const{ return point(x/t,y/t);}
    double length() const { return sqrt(x*x+y*y);};
    point unit()const { double l = length();return point(x/l,y/l); }
};
double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
double dist(const point p1,point p2) { return (p1-p2).length();}
point rotate(point p,double angle,point o = point(0,0))
{   point t = p-o;
    double x = t.x * cos(angle) - t.y*sin(angle);
    double y = t.y * cos(angle) + t.x*sin(angle);
    return point (x,y)+o;
}
struct region{
    double st,ed;
    region(){}
    region(double st,double ed):st(st),ed(ed){}
    bool operator < (const region & rhs)const
    {   if (dblcmp(st-rhs.st)) return st<rhs.st;
    return ed<rhs.ed;
    }
};
struct circle{
    point c;
    double r;
    vector <region>reg;
    circle(){}
    circle(point c,double r):c(c),r(r){}
    void input()
    {
    c.input();
    scanf("%lf",&r);
    }
    void add(const region &r){ reg.PB(r);}
    bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
    bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
};
double sqr( double x){ return x*x;}
void intersection(circle cir1,circle cir2,point &p1,point &p2)
{
    double l = dist(cir1.c,cir2.c);
    double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
    double d2 = sqrt(sqr(cir1.r)-sqr(d));
    point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
    point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
    p1 = mid + v,p2 = mid -v;
}
point calc(const circle &cir,double angle)
{
    point p = point (cir.c.x+cir.r,cir.c.y);
    return rotate(p,angle,cir.c);
}
 
circle cir[N];
bool del[N];
int n;
 
double solve()
{
    double ans = 0 ;
    for ( int i = 0 ; i < n ;  i++){
    for ( int j = 0 ; j < n ; j++) if (!del[j]){
        if (i==j) continue;
        if (cir[j].contain(cir[i]))
        {   del[i] = true;
        break;
        }
    }
    }
    for ( int i = 0 ; i < n ; i++) if (!del[i]){
    circle &mc = cir[i];
    point p1,p2;
    bool flag = false;
    for ( int j = 0 ; j < n ; j++) if (!del[j]){
        if (i==j) continue;
        if (!mc.interect(cir[j])) continue;
        flag = true;
        intersection(mc,cir[j],p1,p2);
        double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
        if (dblcmp(rs)<0) rs+=2*PI;
        if (dblcmp(rt)<0) rt+=2*PI;
        if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
        else mc.add(region(rs,rt));
    }
    if (!flag) { ans += PI*sqr(mc.r); continue;}
    sort(mc.reg.begin(),mc.reg.end());
    int cnt = 1;
    for ( int j = 1 ; j < mc.reg.size() ; j++)
    {
        if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
        mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
        else mc.reg[cnt++] = mc.reg[j];
    }
        mc.add(region());
        mc.reg[cnt]=mc.reg[0];
        for ( int j = 0 ; j < cnt ; j++)
        {
        p1 = calc(mc,mc.reg[j].ed);
        p2 = calc(mc,mc.reg[j+1].st);
        ans +=cross(p1,p2)/2;
        double angle = mc.reg[j+1].st - mc.reg[j].ed;
        if (dblcmp(angle)<0) angle+=2*PI;
        ans+=0.5*sqr(mc.r)*(angle-sin(angle));
        }
    }
    return ans;
    
}
int main()
{
    #ifndef  ONLINE_JUDGE
    freopen("./in.txt","r",stdin);
  #endif
 
    scanf("%d",&n);
    for ( int i = 0 ; i < n ; i++) cir[i].input();
    printf("%.3f\n",solve());
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

 

 

VCIRCLES
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N =1e3+7;
inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
struct point
{
    double x,y;
    point(){}
    point(double x,double y):x(x),y(y){}
    void input(){scanf("%lf%lf",&x,&y);}
    double angle(){ return atan2(y,x);}
    point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
    point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
    point operator * (double t)const{ return point(t*x,t*y);}
    point operator / (double t)const{ return point(x/t,y/t);}
    double length() const { return sqrt(x*x+y*y);};
    point unit()const { double l = length();return point(x/l,y/l); }
};
double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
double dist(const point p1,point p2) { return (p1-p2).length();}
point rotate(point p,double angle,point o = point(0,0))
{   point t = p-o;
    double x = t.x * cos(angle) - t.y*sin(angle);
    double y = t.y * cos(angle) + t.x*sin(angle);
    return point (x,y)+o;
}
struct region{
    double st,ed;
    region(){}
    region(double st,double ed):st(st),ed(ed){}
    bool operator < (const region & rhs)const
    {   if (dblcmp(st-rhs.st)) return st<rhs.st;
    return ed<rhs.ed;
    }
};
struct circle{
    point c;
    double r;
    vector <region>reg;
    circle(){}
    circle(point c,double r):c(c),r(r){}
    void input()
    {
    c.input();
    scanf("%lf",&r);
    }
    void add(const region &r){ reg.PB(r);}
    bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
    bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
};
double sqr( double x){ return x*x;}
void intersection(circle cir1,circle cir2,point &p1,point &p2)
{
    double l = dist(cir1.c,cir2.c);
    double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
    double d2 = sqrt(sqr(cir1.r)-sqr(d));
    point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
    point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
    p1 = mid + v,p2 = mid -v;
}
point calc(const circle &cir,double angle)
{
    point p = point (cir.c.x+cir.r,cir.c.y);
    return rotate(p,angle,cir.c);
}
 
circle cir[N];
bool del[N];
int n;
 
double solve()
{
    double ans = 0 ;
    for ( int i = 0 ; i < n ;  i++){
    for ( int j = 0 ; j < n ; j++) if (!del[j]){
        if (i==j) continue;
        if (cir[j].contain(cir[i]))
        {   del[i] = true;
        break;
        }
    }
    }
    for ( int i = 0 ; i < n ; i++) if (!del[i]){
    circle &mc = cir[i];
    point p1,p2;
    bool flag = false;
    for ( int j = 0 ; j < n ; j++) if (!del[j]){
        if (i==j) continue;
        if (!mc.interect(cir[j])) continue;
        flag = true;
        intersection(mc,cir[j],p1,p2);
        double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
        if (dblcmp(rs)<0) rs+=2*PI;
        if (dblcmp(rt)<0) rt+=2*PI;
        if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
        else mc.add(region(rs,rt));
    }
    if (!flag) { ans += PI*sqr(mc.r); continue;}
    sort(mc.reg.begin(),mc.reg.end());
    int cnt = 1;
    for ( int j = 1 ; j < mc.reg.size() ; j++)
    {
        if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
        mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
        else mc.reg[cnt++] = mc.reg[j];
    }
        mc.add(region());
        mc.reg[cnt]=mc.reg[0];
        for ( int j = 0 ; j < cnt ; j++)
        {
        p1 = calc(mc,mc.reg[j].ed);
        p2 = calc(mc,mc.reg[j+1].st);
        ans +=cross(p1,p2)/2;
        double angle = mc.reg[j+1].st - mc.reg[j].ed;
        if (dblcmp(angle)<0) angle+=2*PI;
        ans+=0.5*sqr(mc.r)*(angle-sin(angle));
        }
    }
    return ans;
    
}
int main()
{
    #ifndef  ONLINE_JUDGE
    freopen("./in.txt","r",stdin);
  #endif
 
    scanf("%d",&n);
    for ( int i = 0 ; i < n ; i++) cir[i].input();
    printf("%.5f\n",solve());
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

 

分类目录模板题 算法学习
标签计算几何

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz