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

Posted by 111qqz on Wednesday, October 11, 2017

TOC

题目链接

题意:

多n个圆的面积并。

思路:

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

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

圆的面积并 

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

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

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

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

以及双倍经验题:SPOJ VCIRCLES

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










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

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付