root :: Regionals 2011 :: Africa/Middle East — Arab Contest problem Fence.....
I have been trying to solve this problem, but I am getting WA , my solution first finds the the length of the cable that covers the edge of any circle. That is I first find for each circle the union of angles according to the tangents, then this angles equals 2pi — ang. And then I find the circles that have at least one incident tangent with an interval not covered by any other circle and I add up this length. here is my solution implemented in c++. I would like to know When my code is failing...thanks in advance..
struct event{ long double ang; int o; event(long double aa,int oo){ ang = aa;o = oo; } bool operator <(const event e) const{ return ang < e.ang; } }; vector E; long double nor(long double ang){ if(ang < 0) return ang + 2.0 * pi; if(ang > 2.0 * pi) return ang — 2.0 * pi; return ang; } void addevent(long double beg,long double end){ if(beg < end){ E.push_back(event(beg — eps / 2.0,1)); E.push_back(event(end,-1)); }else{ E.push_back(event(beg — eps / 2.0,1)); E.push_back(event(2.0 * pi,-1));
E.push_back(event(0.0 - eps / 2.0,1));
E.push_back(event(end,-1));
}
}
long double deg(long double ang){ return ang * 180.0 / pi; } long double dist(int i,int j){ return hypot(X[i] — X[j], Y[i] — Y[j]); }
long double BEG[N]; long double END[N]; long double dists[N];
int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 0;i<n;i++) scanf("%llf%llf%llf",&X[i],&Y[i],&R[i]);
if(n == 1){
printf("%.5llf\n",2.0 * (long double)R[0] * pi);
continue;
}
long double res = 0.0;
long double rr = 0.0;
for(int i = 0;i < n;i++){
E.clear();
for(int j =0 ;j<n;j++){
if(i == j) continue;
long double r1 = R[i];
long double r2 = R[j];
long double d = dist(i,j);
long double ang = nor(atan2(Y[j] - Y[i],X[j] - X[i]));
long double a,ta;
if(r1 == r2){
a = pi / 2.0;
ta = d;
}else if(r1 < r2){
long double d1 = d / (r2 / r1 - 1.0);
a = pi - acos(r1 / d1);
ta = sqrt((d + d1) * (d + d1) - r2 * r2) - sqrt(d1 * d1 - r1 * r1);
}else{
swap(r1,r2);
long double d1 = d / (r2 / r1 - 1.0);
a = acos(r1 / d1);
ta = sqrt((d + d1) * (d + d1) - r2 * r2) - sqrt(d1 * d1 - r1 * r1);
}
long double beg = nor(ang - a);
long double end = nor(ang + a);
addevent(beg,end);
BEG[j] = beg;
END[j] = end;
dists[j] = ta;
}
sort(E.begin(),E.end());
int si = E.size();
long double tot = 0.0;
long double in = 0.0;
int cc = 0;
vector<long double> inter;
if(E[0].ang + 2.0 * pi - E[si - 1].ang > eps ){
inter.push_back(E[0].ang);
inter.push_back(E[si - 1].ang);
}
for(int j =0 ;j<si;j++){
if(E[j].o == 1){
cc++;
if(cc == 1){
if(j != 0)
inter.push_back(E[j].ang);
in = E[j].ang;
}
}else{
cc--;
if(cc == 0){
tot += E[j].ang - in;
if(j != si - 1)
inter.push_back(E[j].ang);
}
}
}
if(fabs(tot - 2.0 * pi) < eps){
continue;
}else{
int ss = inter.size();
for(int k = 0;k<ss;k++){
long double ma = 0;
for(int j = 0;j<n;j++){
if(i == j) continue;
if(fabs(BEG[j] - inter[k] ) < eps || fabs(END[j] - inter[k] ) < eps)
ma = max(ma,dists[j]);
}
rr += ma;
}
tot = 2.0 * pi - tot;
res += (R[i] * tot);
}
}
printf("%.5llf\n",res + rr/2.0);
}
return 0;
}