?? 1688 dolphin pool.cpp
字號:
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<math.h>
#include<assert.h>
using namespace std;
#define NEG 1e-7 //浮點數比較中的允許誤差
struct intersect{ //兩圓交點
int other; //記錄同一交點在另一圓上的位置。other=另一圓序號*100+交點在圓上的序號。
char sign; //相交弧與交點之間的相對位置(順時針或逆時針)
double x, y, x0, y0; //(x,y)是交點坐標,(x0,y0)是圓心坐標
}p[20][40];
struct circle{
int x,y,r;
}cir[20]; //圓
int n,nsec[20]; //圓的個數和每個圓上的交點數目
bool v[20][40]; //交點是否訪問過
/*下面三個函數是快速排序*/
bool operator<(const intersect& x, const intersect& y)
{
return atan2(x.y-x.y0,x.x-x.x0)<atan2(y.y-y.y0,y.x-y.x0)-NEG;
}
int Partition(intersect b[],int l,int r,int a)
{
intersect x=b[l],t;
int i=l-1,j=r+1;
while(1)
{
do{
--j;
}while(x<b[j]);
do{
++i;
}while(b[i]<x);
if(i<j){
p[b[i].other/100][b[i].other%100].other=a*100+j; //排序中加入對other屬性的維護
p[b[j].other/100][b[j].other%100].other=a*100+i;
t=b[i];b[i]=b[j];b[j]=t;
}
else return j;
}
return l;
}
void quicksort(intersect b[],int l,int r,int a)
{
int n;
if(l<r)
{
n=Partition(b,l,r,a);
quicksort(b,l,n,a);
quicksort(b,n+1,r,a);
}
return;
}
/*求兩圓交點*/
void GetPoint(int a,int b,intersect& p1,intersect& p2)
{
int A,B,C,D,E,F;
double A1,B1,C1;
A=-2*cir[a].x;B=-2*cir[a].y;
C=cir[a].x*cir[a].x+cir[a].y*cir[a].y-cir[a].r*cir[a].r;
D=-2*cir[b].x;E=-2*cir[b].y;
F=cir[b].x*cir[b].x+cir[b].y*cir[b].y-cir[b].r*cir[b].r;
if(A==D) //交線平行于x軸
{
p1.y=p2.y=(F-C)/(double)(B-E);
p1.x=(-A+sqrt((double)A*A-4*(p1.y*p1.y+B*p1.y+C)))/2.0;
p2.x=(-A-sqrt((double)A*A-4*(p2.y*p2.y+B*p2.y+C)))/2.0;
}
else if(B==E) //交線平行于y軸
{
p1.x=p2.x=(F-C)/(double)(A-D);
p1.y=(-B+sqrt((double)B*B-4*(p1.x*p1.x+A*p1.x+C)))/2.0;
p2.y=(-B-sqrt((double)B*B-4*(p2.x*p2.x+A*p2.x+C)))/2.0;
}
else //一般情形
{
A1=(double)(E-B)*(E-B)+(double)(A-D)*(A-D);
B1=2.0*(E-B)*(F-C)+((double)D)*(A-D)*(E-B)+(A-D)*(A-D)*(double)E;
C1=(double)(F-C)*(F-C)+((double)D)*(A-D)*(F-C)+((double)F)*(A-D)*(A-D);
p1.y=(-B1+sqrt(B1*B1-4*A1*C1))/(2*A1);
p2.y=(-B1-sqrt(B1*B1-4*A1*C1))/(2*A1);
p1.x=(p1.y*(E-B)+(F-C))/(A-D);
p2.x=(p2.y*(E-B)+(F-C))/(A-D);
}
return;
}
/*判斷焦點p0是否被圓k覆蓋*/
bool Cover(int k,intersect& p0)
{
if((p0.x-cir[k].x)*(p0.x-cir[k].x)+(p0.y-cir[k].y)*(p0.y-cir[k].y)>cir[k].r*cir[k].r+NEG)
return false;
else
return true;
}
/*依序訪問交點,尋找小區域*/
int Visit(int i,int j)
{
double lx,ly,s;
s=0;lx=p[i][j].x;ly=p[i][j].y;
while(!v[i][j])
{
v[i][j]=true;
i=p[i][j].other;
j=i%100;i/=100; //找下一個圓
v[i][j]=true;
if(j<nsec[i]-1)j++; //找下一個交點
else j=0;
s+=(lx*p[i][j].y-ly*p[i][j].x)/2; //計算有向面積
lx=p[i][j].x;ly=p[i][j].y;
} //循環y結束,找到一個由圓弧構成的環
if(s>-NEG)return 0; //有向面積為正,該區域邊界是由多個圓組成的連通區域的外邊界
else return 1; //有向區域為負,該區域是由多個圓圍成的小區域。
}
int main()
{
int t,index,i,j,k;
intersect p1,p2;
cin>>t;
for(index=1;index<=t;index++)
{
/*讀入數據*/
cin>>n;
for(i=0;i<n;i++)
cin>>cir[i].x>>cir[i].y>>cir[i].r;
fill(nsec,nsec+n,0);
/*求交點*/
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
if((cir[i].x-cir[j].x)*(cir[i].x-cir[j].x)+(cir[i].y-cir[j].y)*(cir[i].y-cir[j].y)<(cir[i].r+cir[j].r)*(cir[i].r+cir[j].r))
{
GetPoint(i,j,p1,p2); //求兩圓交點
for(k=0;k<n;k++)
if(k!=i&&k!=j&&Cover(k,p1))break; //判斷交點是否被覆蓋
if(k==n)
{
p[i][nsec[i]].x=p1.x;p[i][nsec[i]].y=p1.y;
p[j][nsec[j]].x=p1.x;p[j][nsec[j]].y=p1.y;
p[i][nsec[i]].x0=cir[i].x;p[i][nsec[i]].y0=cir[i].y;
p[j][nsec[j]].x0=cir[j].x;p[j][nsec[j]].y0=cir[j].y;
p[i][nsec[i]].other=j*100+nsec[j];
p[j][nsec[j]].other=i*100+nsec[i];
//根據兩交點對應半徑的叉積判斷相交弧在交點的順/逆時針方向
if((p1.x-cir[i].x)*(p2.y-cir[i].y)-(p1.y-cir[i].y)*(p2.x-cir[i].x)<-NEG)
{
p[i][nsec[i]].sign='+';p[j][nsec[j]].sign='-';
}
else
{
p[i][nsec[i]].sign='-';p[j][nsec[j]].sign='+';
}
nsec[i]++;nsec[j]++;
}
for(k=0;k<n;k++) //對另一個交點操作,同上
if(k!=i&&k!=j&&Cover(k,p2))break;
if(k==n)
{
p[i][nsec[i]].x=p2.x;p[i][nsec[i]].y=p2.y;
p[j][nsec[j]].x=p2.x;p[j][nsec[j]].y=p2.y;
p[i][nsec[i]].x0=cir[i].x;p[i][nsec[i]].y0=cir[i].y;
p[j][nsec[j]].x0=cir[j].x;p[j][nsec[j]].y0=cir[j].y;
p[i][nsec[i]].other=j*100+nsec[j];
p[j][nsec[j]].other=i*100+nsec[i];
if((p1.x-cir[i].x)*(p2.y-cir[i].y)-(p1.y-cir[i].y)*(p2.x-cir[i].x)<-NEG)
{
p[i][nsec[i]].sign='-';p[j][nsec[j]].sign='+';
}
else
{
p[i][nsec[i]].sign='+';p[j][nsec[j]].sign='-';
}
nsec[i]++;nsec[j]++;
}
}
quicksort(p[i],0,nsec[i]-1,i);
}
fill(&v[0][0],&v[n][0],false);
int s=0;
/*從每個未訪問的交點出發,尋找包含該點的區域*/
for(i=0;i<n;i++)
for(j=0;j<nsec[i];j++)
if(!v[i][j])
if(p[i][j].sign=='-')s+=Visit(i,j);
else s+=Visit(p[i][j].other/100,p[i][j].other%100);
cout<<s<<endl;
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -