UVA - 10969 Sweet Dream
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34782
Problem
上の階からN個の円を落として、円の半径と落点を教えて、最終図形の可視弧の長さの和を求めます.N<=100
Solution
実際には円交差に変換できます.逆にi:n->1,j:i+1->n,iとjの交点(交点がない場合と完全に覆われている場合を考慮しながら)を求め,交点を極角で並べ替えて区間オーバーライド問題となり,いくつかの区間を与え,オーバーライドされていない長さ(この問題では実際には角度)の和を統計し,この円が最終的に表示される弧長を知る.
円と円の交差には特殊なテクニックが必要で、この問題は交点を求める必要はありません.交点の極角を知っていればいいです.極角処理には特殊なテクニックもあり、a<0(aは極角を表す)の場合、a+=2*piである.区間カバーにも特殊なテクニックがあり、リングの場合、すなわち区間がx軸の正方向を通って2つの区間に分解すればよい.
私はやはり、白書の第1章の中で多くのものが非常に重要で、幾何学の中で高い周波数を計算して区間のカバーの問題が現れますと思っています.
具体的にどうするか、コードを見ましょう(主に白書のテンプレートを参考にして、lrjと鳳神コードの指導に感謝します)
My code
Problem
上の階からN個の円を落として、円の半径と落点を教えて、最終図形の可視弧の長さの和を求めます.N<=100
Solution
実際には円交差に変換できます.逆にi:n->1,j:i+1->n,iとjの交点(交点がない場合と完全に覆われている場合を考慮しながら)を求め,交点を極角で並べ替えて区間オーバーライド問題となり,いくつかの区間を与え,オーバーライドされていない長さ(この問題では実際には角度)の和を統計し,この円が最終的に表示される弧長を知る.
円と円の交差には特殊なテクニックが必要で、この問題は交点を求める必要はありません.交点の極角を知っていればいいです.極角処理には特殊なテクニックもあり、a<0(aは極角を表す)の場合、a+=2*piである.区間カバーにも特殊なテクニックがあり、リングの場合、すなわち区間がx軸の正方向を通って2つの区間に分解すればよい.
私はやはり、白書の第1章の中で多くのものが非常に重要で、幾何学の中で高い周波数を計算して区間のカバーの問題が現れますと思っています.
具体的にどうするか、コードを見ましょう(主に白書のテンプレートを参考にして、lrjと鳳神コードの指導に感謝します)
My code
//Hello. I'm Peter.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define MAXN
#define N 2015
#define M
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const double eps=1e-10,pi=acos(-1.0);
inline int dcmp(double x){
if(fabs(x)<eps) return 0;
else if(x<0) return -1;
else return 1;
}
struct Point{
double x,y;
Point(){};
Point(double xx,double yy){
x=xx;
y=yy;
}
};
typedef Point Vector;
double angle(Vector v){
return atan2(v.y,v.x);
}
Vector operator +(const Vector a,const Vector b){
return Vector(a.x+b.x,a.y+b.y);
}
Vector operator -(const Vector a,const Vector b){
return Vector(a.x-b.x,a.y-b.y);
}
double operator *(const Vector a,const Vector b){
return a.x*b.x+a.y*b.y;
}
Vector operator*(const Vector a,const double b){
return Vector(a.x*b,a.y*b);
}
Vector operator*(const double b,const Vector a){
return Vector(a.x*b,a.y*b);
}
double operator%(const Vector a,const Vector b){
return a.x*b.y-a.y*b.x;
}
bool operator==(const Vector a,const Vector b){
return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);
}
double Length(Vector v){
return sqrt(v.x*v.x+v.y*v.y);
}
struct Circle{
double r;
Point c;
Circle(){};
Circle(Point cc,double rr){
c=cc;
r=rr;
}
Point point(double a){
return Point(c.x+r*cos(a),c.y+r*sin(a));
}
}c[N];
inline void CircleInterCircle(Circle c1,Circle c2,double *temp,int& numtemp){
if(!dcmp(c1.r-c2.r)&&c1.c==c2.c){//
numtemp=-1;
return;
}
double dis=Length(c1.c-c2.c);
if(dcmp(dis-(c1.r+c2.r))>=0){
//
numtemp=0;
return;
}
if(dcmp(fabs(c1.r-c2.r)-dis)>=0){
//
if(dcmp(c1.r-c2.r)<=0) numtemp=-1;//c2 c1
else numtemp=0;
return;
}
//
Vector v=c2.c-c1.c;
double a=angle(v);
double b=acos((c1.r*c1.r+dis*dis-c2.r*c2.r)/(2*c1.r*dis));
temp[0]=a+b;
temp[1]=a-b;
numtemp=2;
}
bool PointInCircle(Point p,Circle c){
return dcmp(Length(p-c.c)-c.r)<=0;
}
struct Data{
double a;
bool in;
}data[N];
double temp[10];
int n,numtemp,numdata;
inline bool comp(const Data A,const Data B){
if(dcmp(A.a-B.a)) return A.a<B.a;
else return A.in>B.in;
}
int main(){
int T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf",&c[i].r,&c[i].c.x,&c[i].c.y);
}
double ans=0.0;
for(int i=1;i<=n;i++){
numdata=0;
bool pass=false;
for(int j=i+1;j<=n;j++){
CircleInterCircle(c[i],c[j],temp,numtemp);
if(numtemp==0) continue;
if(numtemp==-1){
pass=true;
break;
}
if(dcmp(temp[0])<0) temp[0]+=2*pi;
if(dcmp(temp[1])<0) temp[1]+=2*pi;
if(dcmp(temp[0]-temp[1])>0) swap(temp[0],temp[1]);
//temp all >0 temp[0]<temp[1]
double mi=(temp[0]+temp[1])*0.5;
Point pmi=c[i].point(mi);
int t;
if(PointInCircle(pmi,c[j])){
t=++numdata;
data[t].a=temp[0];
data[t].in=true;
t=++numdata;
data[t].a=temp[1];
data[t].in=false;
}
else{
t=++numdata;
data[t].a=0;
data[t].in=true;
t=++numdata;
data[t].a=temp[0];
data[t].in=false;
t=++numdata;
data[t].a=temp[1];
data[t].in=true;
t=++numdata;
data[t].a=2*pi;
data[t].in=false;
}
}
if(pass) continue;
double uncover=0.0;
data[++numdata].a=2*pi;
data[numdata].in=false;
sort(data+1,data+1+numdata,comp);
double lasta=0.0;
int num=0;
for(int k=1;k<=numdata;k++){
if(!num) uncover+=data[k].a-lasta;
lasta=data[k].a;
num+=data[k].in?1:-1;
}
uncover*=c[i].r;
ans+=uncover;
}
printf("%.3f
",ans);
}
return 0;
}