Hiển thị các bài đăng có nhãn BÀI TOÁN VỀ ĐOẠN THẲNG. Hiển thị tất cả bài đăng
Hiển thị các bài đăng có nhãn BÀI TOÁN VỀ ĐOẠN THẲNG. Hiển thị tất cả bài đăng

Thứ Hai, 16 tháng 12, 2013

Các tam giác vuông cân



Trên mặt phẳng tọa độ cho N tam giác vuông cân, hai cạnh góc vuông song song với hai trục tọa độ, cạnh huyền nằm ở bên phải tam giác. Cụ thể là nếu kí hiệu tam giác là ABC thì ta qui định đỉnh A là đỉnh góc vuông, cạnh góc vuông AB song song với trục hoành ox, cạnh góc vuông AC song song với trục tung oy, AB = AC = d. Mỗi tam giác được mô tả bằng bộ ba số nguyên x, y, d trong đó (x,y) là tọa độ nguyên của đỉnh A, d là chiều dài cạnh góc vuông.
TAMGIAC.INP
TAMGIAC.OUT
5
6 0 3
1 0 3
2 1 3
4 1 2
4 5 2
16.50

























    y       C




















     





            A


    B





   o


        x 






























Yêu cầu: Tính diện tích do các tam giác phủ trên mặt phẳng tọa độ.

Dữ liệu vào: text file TAMGIAC.INP
Dòng đầu tiên: số tự nhiên N trong khoảng 2 .. 1000.
N dòng tiếp theo: mỗi dòng 3 số x y d cách nhau qua dấu cách, x và y biến thiên trong khoảng -1000..1000, d trong khoảng 1..1000.
Dữ liệu ra: text file TAMGIAC.OUT chứa một số thực duy nhất S là diện tích bị các tam giác phủ trên mặt phẳng tọa độ.

Thuật toán

Tương tự như bài Các Hình chữ nhật. Với mỗi tam giác (x, y, d) ta tạo ra hai đường song song với trục hoành và cắt trục tung tại các điểm y và y+d, cụ thể là một đường chứa cạnh đáy và một đường đi qua đỉnh của tam giác. Các đường thẳng này sẽ tạo ra các băng. Với mỗi tam giác (TG) ta cũng xét tương tự như HCN, nghĩa là xét các băng chứa trong TG đó. Biến diện tích dt được khai báo kiểu float vì các hình trong băng j sẽ là hình thang có đáy lớn là e[j]-s[j], đáy nhỏ bằng đáy lớn – h, h là chiều cao: h = y[j+1]-y[j] = độ rộng của băng. Khi chuyển từ băng j lên băng j+1 ta phải chỉnh lại đầu phải x2 của cạnh đáy TG thành x2 – h vì TG lúc này sẽ ngắn lại. Khi tính phần giao nhau ta còn phải trừ đi diện tích của TG nằm ngoài phần giao  đó.  Hình vẽ cho ta thấy khi xét tam giác XYV và băng giới hạn trong 2 đường thẳng TM và SE, thì làn (S, E) sẽ được mở rộng thành làn (S, V). Diện tích trước đó của làn SE chính là diện tích hình thang vuông TMES, nay làn (S,V) có diện tích của hình thang vuông TRVS. Như vậy ta đã tính dôi ra phần diện tích tam giác MPQ.  Dễ dàng xác định được diện tích z của tam giác vuông cân này: Đặt k = MP = PQ, ta có z = k2/2.Ta xác định k như sau. k = MP =  TP - TM = SX-TM = x-(e[j]-h), trong đó h là chiều rộng của băng j đang xét, h =  y[j+1]-y[j], e[j] là điểm cuối của làn đang xét, x là hoành độ  của đỉnh góc vuông trong tam giác XYV đang xét.
Độ phức tạp: N2.
(* Pascal *)
(**********************************************
           Cac tam giac vuong can
 *********************************************)
program TamGiacVuongCan;
uses crt;
const mn = 2001; bl = #32; nl = #13#10;
fn = 'TamGiac.inp'; gn = 'TamGiac.out';
type TG = record
            x,y: integer;
            d: integer;
          end;
     mtg1 = array[0..mn] of TG;
     mi1 = array[0..mn] of integer;
     mr1 = array[0..mn] of real;
var
  n,m: integer; { n - so tam giac }
  y: mi1;       { m - so diem y, max(m) = 2n }
  t: mtg1;
  f,g: text;
  dt: real; // tong dien tich
  (*--------------------------------------------
    To chuc du lieu cho Bang i
     s[i], e[i] - can trai va phai cua Bang
  ----------------------------------------------*)
  s, e: mi1;
function Max(a,b: integer): tự viết
(*-----------------------------
   Xen them v vao day
   da sap tang y[1..m]
 ------------------------------*)
procedure Insert(v: integer); tự viết
procedure Doc;
var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n);
  m := 0;
  for i := 1 to n do
   begin
    readln(f,t[i].x,t[i].y,t[i].d);
    Insert(t[i].y); Insert(t[i].y + t[i].d);
   end;
  close(f);
end;
{ Sap cac TG tang theo x }
procedure SortByX(d,c: integer); tự viết
{ Tim nhi phan v trong y[1..m] }
function BinSearch(v: integer): integer; tự viết
(*---------------------------------------
   Xet hinh Tam giac h: tinh cac o
   hinh h phu tren cac Bang
   --------------------------------------*)
procedure Hinh(x1,y1,d: integer);
 var i,y2,x2,h,k: integer;
begin
  { Tim xuat hien cua toa do y1 trong cac lan }
  i := BinSearch(y1);
  x2 := x1 + d; y2 := y1 + d;
  while (y[i] < y2) do
    begin
     h := y[i + 1] - y[i];
     if (x1 <= e[i]) then
      begin
       k := x1 - (e[i] - h); e[i] := Max(e[i], x2);
       if (k > 0) then dt := dt - (real(k * k) / 2);
      end
     else
      begin
        if (e[i] > s[i]) then
           dt  := dt + h * (2 * (e[i] - s[i]) - h) / 2;
        s[i] := x1; e[i] := x2;
      end;
     i := i + 1; x2 := x2 - h;
   end;
end;
procedure XuLi;
 var i, h: integer;
begin
 for i := 1 to m do
  begin s[i] := -maxint; e[i] := s[i]; end;
  dt := 0.0;
  { Duyet cac TG }
  for i := 1 to n do Hinh(t[i].x,t[i].y,t[i].d);
  { Tong hop ket qua }
  for i := 1 to m-1 do
    begin
      h := y[i + 1] - y[i];
      if (e[i] > s[i]) then
        dt := dt +  h * (2 * (e[i] - s[i]) - h) / 2;
    end;
end;
procedure Ghi;
begin
  assign(g,gn); rewrite(g); writeln(g,dt:0:2); close(g)
end;
BEGIN
  Doc; SortByX(1,n); XuLi; Ghi;
END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH


Các hình chữ nhật



Trên mặt phẳng tọa độ cho N hình chữ nhật (HCN) có diện tích khác 0 và có các cạnh song song với các trục tọa độ. Mỗi HCN được mô tả bằng bộ bốn số nguyên (x1,y1) và (x2,y2) biểu thị tọa độ nguyên của hai đỉnh đối diện.  
Yêu cầu: xác định diện tích phần mặt phẳng  bị các HCN phủ.

HCN.INP
HCN.OUT

Dữ liệu vào: tệp văn bản HCN.INP
Dòng đầu tiên: số tự nhiên 1 < N £ 1000.
Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa 4 số nguyên x1, y1, x2, y2 cách nhau qua dấu cách.
Dữ liệu ra: tệp văn bản HCN.OUT chứa tổng đơn vị diện tích trên mặt phẳng bị các HCN phủ.


5
0 0 2 4
1 2 4 6
5 3 3 7
4 1 6 5
7 3 9 0

35

Thuật toán

Phương pháp: Tham.



y2
A

B








y1




D

C


x1
x2
1. Đọc dữ liệu và chỉnh lại các tọa độ sao cho
x1 £ x2 và y1 £ y2. Điều này có nghĩa là ta qui ước mọi HCN ABCD đều được xác định qua 2 đỉnh đối diện D (đỉnh Tây-Nam) và B (đỉnh Đông-Bắc): D(x1, y1), B(x2, y2).
Khi đọc dữ liệu ta đồng thời lược bớt các giá trị y trùng lặp và sắp các giá trị y1 và y2 theo chiều tăng để ghi vào một mảng y[1..m]. Như vậy, giá trị lớn nhất của m là 2n. Ta gọi phần mặt phẳng giới hạn bởi hai đường thẳng song song với trục hoành và cắt trục tung tại điểm y[i] và y[i+1] là băng i. Ta có m-1 băng mã số từ 1 đến m-1. Băng đầu tiên có mã số 1 nằm giữa hai đường y[1] và y[2], băng cuối cùng có mã số m-1 nằm giữa hai đường y[m-1] và y[m]. Nhiệm vụ còn lại là tính diện tích bị phủ trên mỗi băng. Tổng số diện tích bị phủ của các băng sẽ là đáp số cho bài toán.
2. Ta lại sắp các HCN theo chiều tăng của tọa độ x1.
3. Với mỗi HCN h(x1, y1, x2, y2) ta xét các băng i trong khoảng từ y1 đến y2. Với băng i giả sử ta đã biết phần bị các HCN 1..(h-1) phủ trên băng này. Ta kí hiệu s[i] và e[i] là giới hạn hoành độ trái và phải của phần đang bị phủ trên băng i. Diện tích hiện bị phủ trên băng i sẽ là: (y[i+1]-y[i])*(e[i] – s[i]), trong đó y[i+1] – y[i] là chiều rộng của băng i. Ta cần chỉnh lại phần bị phủ trong băng i khi xét thêm HCN h(x1, y1, x2, y2). Dễ thấy, nếu x1 nằm giữa s[i] và e[i] thì ta cần chỉnh lại e[i] theo công thức e[i] := max(e[i], x2). Ngược lại, nếu x1 > e[i] thì ta kết thúc làn (s[i],e[i]) này như sau: Tính diện tích làn này và đưa vào biến tích lũy diện tích dt sau đó đặt lại cận s[i] := x1; e[i] := x2.
Do các hoành độ y1 và y2  được sắp tăng nên ta có thể gọi thủ tục tìm kiếm nhị phân BínSearch để xác định băng chứa y1.
Độ phức tạp: Các thuật toán sắp xếp và chèn đòi hỏi tối đa N2, Thủ tục xử lí xét mỗi HCN 1 lần và duyệt 2n băng. Tổng hợp: N2.
(* Pascal *)
(**********************************************
              Cac hinh chu nhat
     
 *********************************************)
program HinhChuNhat;
uses crt;
const mn = 2001; fn = 'HCN.INP'; gn = 'HCN.OUT';
      bl = #32; nl = #13#10;
type CN = record
            x1, y1: integer;
            x2, y2: integer;
          end;
      mcn1 = array[0..mn] of CN;
      mi1 = array[0..mn] of integer;
var
  n,m: integer; { n - so HCN, m - so lan }
  h: mcn1; { cac HCN }
  y: mi1; { ranh gioi cac lan }
  s, e: mi1; { Cac diem dau va cuoi cua bang }
  f,g: text;
  dt: Longint;
function Max(a,b: integer): tự viết
(*-----------------------------
     Hoán đổi trị để a £ b
------------------------------*)
procedure Chinh(var a,b: integer);
  var c: integer;
begin
  if (a > b) then begin  c := a; a := b; b := c;  end;
end;
(*------------------------------------
     Tim nhi phan v trong y[1..m]
-------------------------------------*)
function BinSearch(v: integer): integer;
var d,c,t: integer;
begin
   d := 1 ; c := m;
   while (d < c) do
   begin
     t := (d + c) div 2;
     if (y[t] < v) then d := t + 1
       else c := t;
   end;
   BinSearch := d;
end;
(*-----------------------------
   Xen them v vao day
   da sap tang y[1..m]
 ------------------------------*)
procedure Insert(v: integer);
var d: integer;
begin
  if (m = 0) then { danh sach rong }
   begin m := m + 1;  y[m] := v;  exit; end;
  d := BínSearch(v);
  if (y[d] =  v) then exit; { da co trong danh sach }
  if (y[d] < v) then begin m := m + 1; y[m] := v; exit; end;
  move(y[d], y[d+1],sizeof(integer)*(m-d+1));
  y[d] := v;  m := m + 1;
end;
(*-------------------------------
   Doc du lieu va sap theo Y
   luoc bot cac Y bang nhau
  ------------------------------*)
procedure Doc;
var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n); m := 0;
  for i := 1 to n do
    begin
      readln(f,h[i].x1,h[i].y1,h[i].x2,h[i].y2);
      Chinh(h[i].x1, h[i].x2); Chinh(h[i].y1, h[i].y2);
      insert(h[i].y1); insert(h[i].y2);
    end;
  close(f);
end;
procedure SortByX1(d,c: integer);
var i,j,m: integer;
    v: CN;
begin
  i := d; j := c;
  m := h[(i+j) div 2].x1;
  while (i <= j) do
  begin
    while (h[i].x1 < m) do i := i + 1;
    while (m < h[j].x1) do j := j - 1;
    if (i <= j) then
     begin
        v := h[i]; h[i] := h[j]; h[j] := v;
        i := i + 1; j := j - 1;
     end;
  end;
  if (d < j) then SortByX1(d,j);
  if (i < c) then SortByX1(i,c);
end;
(*----------------------------------
    Xet HCN d, tinh tung phan
    phu trong moi lan
------------------------------------*)
procedure Hinh(x1, x2, y1, y2: integer);
 var i: integer;
begin
  { Tim xuat hien cua y1 trong cac lan }
  i := BinSearch(y1);
  while (y[i] < y2) do
    begin
     if (x1 <= e[i]) then
       e[i] := Max(e[i], x2)
     else
      begin
        dt := dt + (e[i] - s[i]) * (y[i+1] - y[i]);
        s[i] := x1; e[i] := x2;
      end;
     i := i + 1;
   end;
end;
procedure XuLi;
 var d: integer;
begin
  { Khoi tri }
  dt := 0;
  for d := 1 to m-1 do
  begin s[d] := -maxint; e[d] := s[d];  end;
  { Duyet cac HCN }
  for d := 1 to n do
      Hinh(h[d].x1, h[d].x2, h[d].y1, h[d].y2);
  { Tong hop ket qua }
  for d := 1 to m-1 do
     dt := dt +  (e[d] - s[d]) * (y[d+1] - y[d]);
end;
procedure Ghi;
begin
  assign(g,gn); rewrite(g); writeln(g,dt); close(g)
end;
BEGIN
  Doc; SortByX1(1,n);  XuLi;  Ghi;
END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH