1  // Fly Swatter                             Bill Rubin
   2  using System;
   3  using System.Diagnostics;
   4  /*
   5  Strategy:
   6  	1. Probability of hitting fly is 1 - probability of missing the fly.
   7      2. Probability of missing the fly is area where fly can fit divided by total area.
   8  	3. Assume origin at center of racquet.  By symmetry, need compute only
   9         sector from 0 to pi/4 (1/8 of circle).
  10  	4. Area in sector where fly misses is sum of squares and truncated squares
  11  	   in sector where fly misses.   
  12  */
  13  class TestCase {
  14      public TestCase(double f, double R, double t, double r, double g) {
  15  
  16          // Input checks:
  17          double max = 10000;
  18          Debug.Assert(f > 0 && f <= max, "Valid input");
  19          Debug.Assert(R > 0 && R <= max, "Valid input");
  20          Debug.Assert(t > 0 && t <= max, "Valid input");
  21          Debug.Assert(r > 0 && r <= max, "Valid input");
  22          Debug.Assert(g > 0 && g <= max, "Valid input");
  23  
  24          // Inputs:
  25          R_ = R;
  26  
  27  		// Convenience constants:
  28          hitLength_ = r + f;
  29  		missLength_ = g - 2*f;
  30          pitch_ = g + 2*r;  // Pitch is sum of hit length and miss length
  31  		missArea_ = Math.Pow(missLength_, 2);
  32          maxRadius2_ = Math.Pow(R - t - f, 2);
  33  
  34          // Accumulated variable:
  35          totalMissArea_ = 0;
  36          }
  37  
  38  	public double getProbability() {
  39  		double areaOfSector = Math.PI*Math.Pow(R_, 2)/8;  // 1/8 of circle
  40  		double probability = 1 - totalMissArea_/areaOfSector;
  41          Debug.Assert(probability>=0 && probability<=1, "Valid probability");
  42          return probability;    
  43  		}
  44  
  45       private double getDelta(double vertex, double angle) {
  46          // Use law of cosines to return delta (small side)
  47          double asin = vertex * Math.Sin(angle);
  48          double discr12 = Math.Sqrt(maxRadius2_ - Math.Pow(asin, 2));
  49          double term = vertex * Math.Cos(angle);
  50          // If term < 0, angle is oblique and must take positive sign of discr12.
  51          // Else, must take negative sign of discr12.
  52          double delta = term < 0 ? term + discr12 : term - discr12;
  53          Debug.Assert(delta>0, "Delta is positive");
  54          return delta;
  55          }
  56  
  57      private double getSegmentArea(double deltaX, double deltaY) {
  58          // Inputs are sides of a right triangle whose hypotenuse is the chord
  59          // Therefore, sum of squares of sides is square of chord
  60          // Apply law of cosines:
  61          double cos = 1 - (Math.Pow(deltaX, 2) + Math.Pow(deltaY, 2)) / (2 * maxRadius2_);
  62          Debug.Assert(cos>=0 && cos<=1, "Angle is acute");
  63          double segmentAngle = Math.Acos(cos);
  64          // Formula for area of segment:
  65          return (segmentAngle - Math.Sin(segmentAngle)) * maxRadius2_ / 2;
  66          }
  67  
  68      public void execute() {
  69  		if(missLength_<=0) return;  // Fly is too big to miss.
  70  
  71  		// Compute number n of squares on X-axis
  72  		int n = 1 + (int)Convert.ChangeType(Math.Ceiling(R_/pitch_), typeof(int));
  73          Debug.Assert(n<=500, "n unexpectedly large");
  74  
  75  		for (int x = 0; x < n; x++) {
  76  			for (int y = 0; y<=x ; y++) { // Ignore squares above diagonal.
  77                  double areaOfTruncatedSquare = 0; // To be set to area of this square or partial square
  78  
  79                  // Coordinates of fly in hole extrema:
  80                  double leftX = x * pitch_ + hitLength_;
  81                  double bottomY = y * pitch_ + hitLength_;
  82                  double rightX = (x + 1) * pitch_ - hitLength_;
  83                  double topY = (y + 1) * pitch_ - hitLength_;
  84  
  85                  double leftX2 = Math.Pow(leftX, 2);
  86                  double rightX2 = Math.Pow(rightX, 2);
  87                  double bottomY2 = Math.Pow(bottomY, 2);
  88                  double topY2 = Math.Pow(topY, 2);
  89  
  90                  bool isFullyInsideRacquet = maxRadius2_ >= rightX2 + topY2;
  91                  bool isFullyOutsideRacquet = maxRadius2_ <= leftX2 + bottomY2;
  92  
  93                  if(isFullyInsideRacquet) areaOfTruncatedSquare = missArea_;
  94                  else if(!isFullyOutsideRacquet) {
  95                      // Square is partially inside (truncated).
  96                      double leftBottom = Math.Sqrt(leftX2 + bottomY2);
  97                      double leftTop = Math.Sqrt(leftX2 + topY2);
  98                      double rightTop = Math.Sqrt(rightX2 + topY2);
  99  
 100                      bool topLeftIsOutside = maxRadius2_ <= leftX2 + topY2;
 101                      bool bottomRightIsOutside = maxRadius2_ <= rightX2 + bottomY2;
 102  
 103                      if (topLeftIsOutside) { // Intersects bottom and left ==> Triangle + segment
 104                          double inclination = Math.Atan(bottomY / leftX);
 105                          double deltaX = getDelta(leftBottom, Math.PI - inclination);
 106                          double deltaY = getDelta(leftBottom, Math.PI / 2 + inclination);
 107                          double triangle = deltaX * deltaY / 2;
 108                          areaOfTruncatedSquare = triangle + getSegmentArea(deltaX, deltaY);
 109                      }
 110                      else if (bottomRightIsOutside) { // Intersects bottom and top ==> Parallelogram + segment
 111                          double inclinationBottom = Math.Atan(bottomY / leftX);
 112                          double inclinationTop = Math.Atan(topY / leftX);
 113                          double deltaXbottom = getDelta(leftBottom, Math.PI - inclinationBottom);
 114                          double deltaXtop = getDelta(leftTop, Math.PI - inclinationTop);
 115                          double parallelogram = (deltaXtop + deltaXbottom) * missLength_ / 2;
 116                          areaOfTruncatedSquare = parallelogram + getSegmentArea(deltaXbottom - deltaXtop, missLength_);
 117                      }
 118                      else { // Intersects right and top ==> all - Triangle + segment
 119                          double inclination = Math.Atan(topY / rightX);
 120                          double deltaX = getDelta(rightTop, inclination);
 121                          double deltaY = getDelta(rightTop, Math.PI / 2 - inclination);
 122                          double triangle = deltaX * deltaY / 2;
 123                          areaOfTruncatedSquare = missArea_ - triangle + getSegmentArea(deltaX, deltaY);
 124                      }
 125                  }
 126  
 127                  // If on diagonal, use only half of areaOfTruncatedSquare:
 128                  totalMissArea_ += x==y ? areaOfTruncatedSquare / 2
 129                                         : areaOfTruncatedSquare;
 130                  }
 131  			}
 132          }
 133  
 134      // ======= Data Members ========
 135  	// Inputs:
 136      private double R_;
 137  
 138  	// Other constants:
 139      private double hitLength_;
 140  	private double missLength_;
 141      private double pitch_;
 142  	private double missArea_;
 143      private double maxRadius2_;
 144  
 145  	// Output (before transformation):
 146  	private double totalMissArea_;
 147  }