Phân tích

Đây là bài toán khó nhất trong bộ đề này, như có thể thấy từ thống kê bài nộp, nhưng vẫn có 652 người giải đúng.

Bước đầu tiên để giải bài toán này liên quan đến một kỹ thuật chuẩn. Thay vì tìm vùng mà thân hình cầu của con ruồi sẽ va chạm, chúng ta tìm vùng mà tâm của con ruồi phải tránh. Bài toán được chuyển đổi thành một bài toán tương đương, nơi chúng ta làm dày kích thước của vành vợt thành \(t + f\) và bán kính của các sợi dây từ \(r\) thành \(r + f\). Khi đó, chúng ta coi con ruồi chỉ đơn giản là một điểm duy nhất và chỉ tập trung vào tâm của nó.

Bây giờ vấn đề chính là tìm diện tích của các lỗ hổng (vùng nằm giữa các dây, hoặc giữa các dây và vành vợt), sau đó chia nó cho diện tích của hình tròn tương ứng với bán kính ngoài của vợt ban đầu. Dễ thấy điều này cho chúng ta xác suất mà vợt không đánh trúng con ruồi.

Một quan sát giúp đơn giản hóa là chúng ta chỉ cần xét góc phần tư thứ nhất của hình tròn vì chiếc vợt có tính đối xứng.

Bây giờ chúng ta có thể duyệt qua từng ô trống hình vuông trong vợt và kiểm tra một vài trường hợp. Mỗi trường hợp bao gồm việc tính toán diện tích giao nhau giữa hình vuông và hình tròn đại diện cho phía trong của vành vợt. Trường hợp hình vuông hoàn toàn nằm trong hoặc hoàn toàn nằm ngoài hình tròn là dễ dàng. Các trường hợp còn lại là khi có một, hai hoặc ba góc của hình vuông nằm trong hình tròn và các góc khác nằm ngoài. Không còn trường hợp nào khác vì chúng ta chỉ xét phần giao của một phần tư hình tròn với các hình vuông nhỏ.

Mỗi trường hợp này có thể được giải quyết bằng cách chia diện tích giao nhau thành các hình tam giác và một hình viên phân. Dưới đây là đoạn mã thực hiện việc này:

double circle_segment(double rad, double th) {
  return rad*rad*(th - sin(th))/2;
}

double rad = R-t-f;
double ar = 0.0;
for (double x1 = r+f; x1 < R-t-f; x1 += g+2*r)
for (double y1 = r+f; y1 < R-t-f; y1 += g+2*r) {
  double x2 = x1 + g - 2*f;
  double y2 = y1 + g - 2*f;
  if (x2 <= x1 || y2 <= y1) continue;
  if (x1*x1 + y1*y1 >= rad*rad) continue;
  if (x2*x2 + y2*y2 <= rad*rad) {
    // All points are inside circle.
    ar += (x2-x1)*(y2-y1);
  } else if (x1*x1 + y2*y2 >= rad*rad &&
             x2*x2 + y1*y1 >= rad*rad) {
    // Only (x1,y1) inside circle.
    ar += circle_segment(rad, acos(x1/rad) - asin(y1/rad)) +
          (sqrt(rad*rad - x1*x1)-y1) *
          (sqrt(rad*rad - y1*y1)-x1) / 2;
  } else if (x1*x1 + y2*y2 >= rad*rad) {
    // (x1,y1) and (x2,y1) inside circle.
    ar += circle_segment(rad, acos(x1/rad) - acos(x2/rad)) +
          (x2-x1) * (sqrt(rad*rad - x1*x1)-y1 +
                     sqrt(rad*rad - x2*x2)-y1) / 2;
  } else if (x2*x2 + y1*y1 >= rad*rad) {
    // (x1,y1) and (x1,y2) inside circle.
    ar += circle_segment(rad, asin(y2/rad) - asin(y1/rad)) +
          (y2-y1) * (sqrt(rad*rad - y1*y1)-x1 +
                     sqrt(rad*rad - y2*y2)-x1) / 2;
  } else {
    // All except (x2,y2) inside circle.
    ar += circle_segment(rad, asin(y2/rad) - acos(x2/rad)) +
          (x2-x1)*(y2-y1) -
          (y2-sqrt(rad*rad - x2*x2)) *
          (x2-sqrt(rad*rad - y2*y2)) / 2;
  }
}
printf("Case #%d: %.6lf\n", prob++, 1.0 - ar / (PI*R*R/4));

Giải pháp này mất thời gian \(O(S^2)\), trong đó \(S\) là số lượng dây dọc của vợt. Không khó để đưa ra một giải pháp \(O(S)\) vì có tối đa \(4S\) ô vuông biên có thể được tìm thấy một cách hiệu quả, nhưng giải pháp trước đó đã đủ nhanh.

Thay vì giải bài toán một cách chính xác, một giải pháp lặp xấp xỉ diện tích đến độ chính xác cần thiết cũng có thể hoạt động. Một giải pháp như vậy sử dụng chia để trị bằng cách chia hình vuông thành bốn hình vuông nhỏ hơn và sau đó kiểm tra các trường hợp đơn giản khi các hình vuông hoàn toàn nằm trong hoặc hoàn toàn nằm ngoài. Trong các trường hợp hình tròn và hình vuông giao nhau, chỉ cần đệ quy nếu hình vuông hiện tại lớn hơn một độ chính xác đã chọn. Một quan sát là chúng ta có thể chia mọi độ dài cho bán kính của vợt vì nó sẽ bị triệt tiêu trong phép chia giữa diện tích các khoảng trống và diện tích hình tròn. Quan sát này giúp ích cho giải pháp lặp vì chúng ta có thể làm cho số lần lặp nhỏ hơn. Dưới đây là mã mẫu:

double intersection(double x1, double y1,
                    double x2, double y2) {
  // the normalized radius is 1
  if (x1*x1 + y1*y1 > 1) {
    return 0;
  }
  if (x2*x2 + y2*y2 < 1) {
    return (x2-x1) * (y2-y1);
  }
  // EPS2 = 1e-6 * 1e-6
  if ((x2-x1)*(y2-y1) < EPS2) {
    // this trick helps in doing 10 or 100 times less
    // iterations than we would need to get the same
    // precision if we just return 0;
    return (x2-x1) * (y2-y1) / 2;
  }

  double mx = (x1 + x2) / 2;
  double my = (y1 + y2) / 2;

  return intersection(x1, y1, mx, my) +
    intersection(mx, y1, x2, my) +
    intersection(x1, my, mx, y2) +
    intersection(mx, my, x2, y2);
}

Dựa trên phân tích chính thức của Google Code Jam.