1 bài hay!

[haplinhavxt]

Hôm qua đang yên, bỗng ngồi chế ra 1 bài cực hay, các bạn xem và nghĩ cách giải nha:
Cho 2 hình tròn, tìm diện tích phần chung của 2 hình tròn này.
Input: 2 cặp điểm x, y, r ; trong đó (x, y) là tọa độ tâm, r là bán kính.
Output: Kết quả làm tròn 5 chữ số thập phân.
Timelimit: ko có gì phải nói cho 0.0000001s cho nó oách!

[hoctin.net1]

lâu ko ddoojngj vào pC quên khối, thấy bài này bt mà,
1. vẽ hình và tim công thức
2. từ công thức đó tính ra giấy diện tích chung
3. hoàn thành code pac thôi, đơn giản vậy thôi, hihi

[haplinhavxt]

Nói thì dễ lắm, bây giờ chỉ cần bạn tìm cái công thức đi )

[haibet]

chắc làm ko đúng chỗ nào rùi, chứ hay j` đâu...

[haplinhavxt]

uk thì ko hay, vậy bạn thử nói cách làm xem nào>

[HGMinh95]

Đây là đáp án:

[haplinhavxt]

uk nhỉ nhầm tí, cứ tưởng khó ai ngờ, chết ở cái ko vẽ và làm thử mà! Có 1 bài khác chắc khó hơn, ta thay 1 hình tròn bên trên = 1 hình chữ nhật!

[Em Chán Gà]

Bài toán 1.Trong mặt phẳng toạ độ cho trước toạ độ tâm và độ dài bán kính của hai đường tròn. Hãy tìm diện tích phần giao và diện tích phần hợp của chúng. Dữ liệu vào cho trong file CIRCLE.INP gồm hai dòng, mỗi dòng chứa 3 số theo thứ tự là hoành độ, tung độ và bán kính của đường tròn. Dữ liệu ra ghi vào file CIRCLE.OUT gồm hai dòng, dòng đầu tiên ghi một số thực là diện tích phần giao, dòng tiếp theo ghi diện tích phần hợp (các số thực được lấy chính xác đến hai chữ số thập phân). Ví dụ:

CIRCLE.INP

0 0 1

0 0 3

CIRCLE.OUT

3.12

28.30

Thuật toán tìm diện tích phần giao (hay còn gọi là phương pháp chia lưới): Chia mặt phẳng ra thành một lưới các ô vuông bởi các đường thẳng song song với các trục toạ độ. Kiểm tra từng ô vuông, nếu nó nằm trong cả hai đường tròn (thuộc phần giao của hai đường tròn) thì ta cộng thêm vào giá trị diện tích cần tìm một lượng bằng diện tích của ô vuông đó.

Một số lưu ý với phương pháp này:

- Phương pháp này có thể mở rộng để tìm diện tích phần giao và phần hợp của tập gồm nhiều đối tượng bất kỳ như đa giác, đường tròn, elíp...Điểm quan trọng là ta phải xác định được điều kiện để kiểm tra một ô vuông có thuộc miền trong của đối tượng không.

- Phương pháp này chỉ cho kết quả gần đúng. Kích thước các ô vuông của lưới càng nhỏ thì độ chính xác càng cao nhưng tốc độ thực hiện lại chậm đi.

- Cần có kỹ thuật duyệt để hạn chế số lượng hay khoanh vùng các ô vuông nhỏ cần kiểm tra. Chẳng hạn, với bài toán trên thì rõ ràng ta chỉ cần duyệt các ô vuông nằm trong một hình vuông ngoại tiếp một trong hai đường tròn.

Thuật toán tìm phần hợp của hai đường tròn rất đơn giản là ta chỉ việc lấy diện tích của tổng hai đường tròn rồi trừ đi phần diện tích giao nhau (hoặc cũng có thể thay vì kiểm tra điều kiện ô vuông phải nằm trong cả hai đường tròn thì ta chỉ cần kiểm tra nó có thuộc một đường tròn nào đó không).Để thực hiện thao tác chia mặt phẳng thành lưới ô vuông, ta dùng hai vòng lặp lồng nhau với hai biến điều khiển để duyệt trên các cạnh của lưới. Dưới đây là chương trình minh hoạ cho thuật toán tìm diện tích phần giao của hai dường tròn (để đơn giản, ta coi một ô vuông là thuộc đường tròn nếu đỉnh trên bên trái của nó thuộc đường tròn đó).

[Em Chán Gà]

Đây là Code, Mình chỉ sưu tầm, chưa test vì máy ko có pascal.

Program tinh_dien_tich_phan_giao_hai_duong_tron;
 Var
   x1,y1,x2,y2,i,j,r1,r2,k,h,s:real;

Function dist(x,y,u,v:real):real;
{distance between (x,y) and (u,v)}
  Begin
  dist:=sqrt(sqr(x-u)+sqr(y-v));
  End;
Procedure init;
  Var f :text;
  Begin
   assign(f,'circle.inp');
   reset(f);
   read(f,x1,y1,r1);
   read(f,x2,y2,r2);
   close(f);
   s:=0
  End;
Procedure result;
  Var f :text;
  Begin
   assign(f,'circle.out');
   rewrite(f);
   writeln(f,s:5:2);
   writeln(f,pi*(r1*r1+r2*r2)-s:5:2);
   close(f);
  End;

Procedure solve;

Begin
  init;
  if dist(x1,y1,x2,y2)
  i:=x1-r1;k:=x1+r1;
  h:=y1+r1;
  while i
   begin
    j:=y1-r1;
    while j
      begin
        if dist(i,j,x1,y1)
          if dist(i,j,x2,y2)
            j:=j+0.05;
  end;

i:=i+0.05;

end;

result;

end;

begin

solve;

end.