https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=524&page=show_problem&problem=4023

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;

}