Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 2 - Chương 1: Các bài toán về đoạn thẳng

 static public void Ghi() 
 { File.WriteAllText(gn,dt.ToString()); } 
 static public void XemKetQua(): tự viết 
 static public void XuLi(){ 
 dt = 0; // tong dien tich 
 int[] s = new int[m]; // diem dau cac bang 
 int [] e = new int [m]; // diem cuoi cac bang 
 for (int i = 0; i < m; ++i) 
 s[i] = e[i] = int.MinValue; 
 // Duyet cac HCN 
 for (int i = 0; i < n; ++i) { // xu li HCN i 
 int sj = BinSearch(c[i].y1); 
 int ej = BinSearch(c[i].y2); 
 for (int j = sj; j < ej; ++j){ // xet bang j 
 if (c[i].x1 <= e[j]) e[j] = Max(e[j], c[i].x2); 
 else { 
 dt += (e[j] - s[j])*(y[j+1]-y[j]); 
 s[j] = c[i].x1; e[j] = c[i].x2; 
 } 
 } 
 } 
 // Tong hop ket qua 
 int m1 = m - 1; 
 for (int j = 0; j < m1; ++j) 
 dt += (e[j] - s[j])*(y[j+1]-y[j]); 
 } 
 static public int Max(int a, int b): tự viết 
 static public void Doc() { 
 int[] v = 
 Array.ConvertAll(((File.ReadAllText(fn))).Split( 
 new chae[] { ' ', '\t', '\r', '\n' }, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 int j = 0; n = v[j]; 
 c = new HCN[n]; 
 int dx, dy, bx, by, t; 
 m = 0; 
 y = new int[2*n]; 
 for (int i = 0; i < n; ++i, j += 4) { 
 dx = v[j + 1]; dy = v[j + 2]; 
 bx = v[j + 3]; by = v[j + 4]; 
 if (dx > bx) { t = dx; dx = bx; bx = t; } 
 if (dy > by) { t = dy; dy = by; by = t; } 
 46 
 c[i] = new HCN(dx, dy, bx, by); 
 Insert(dy); Insert(by); 
 } 
 } 
 // Tim nhi phan gia tri v trong y[0..m-1] 
 static public int BinSearch(int v) { 
 int left = 0, right = m-1, midle; 
 while (left < right) { 
 midle = (left + right)/2; 
 if (y[midle] < v) left = midle + 1; 
 else right = midle; 
 } 
 return left; 
 } 
 // Xen toa do v vao danh sach cac lan y 
 static public void Insert(int v) { 
 if (m == 0) { y[m++] = v; return; } 
 int i = BinSearch(v); 
 if (y[i] == v) return; 
 if (y[i] < v) { y[m++] = v; return; } 
 Array.Copy(y, i, y, i + 1, m - i); 
 y[i] = v; ++m; 
 } 
 // Sap cac HCN tang theo x1 
 static public void QSortByx1(int s, int e) { 
 int i = s, j = e, m = c[(i + j) / 2].x1; 
 HCN t; 
 while (i <= j) { 
 while (c[i].x1 < m) ++i; 
 while (c[j].x1 > m) --j; 
 if (i <= j) { 
 t = c[i]; c[i] = c[j]; c[j] = t; 
 ++i; --j; 
 } 
 } 
 if (s < j) QSortByx1(s, j); 
 if (i < e) QSortByx1(i, e); 
 } 
 } // Hcn 
 public struct HCN { 
 public int x1,y1,x2,y2; 
 public HCN(int dx, int dy, int bx, int by) 
 { x1 = dx; y1 = dy; x2 = bx; y2 = by; } 
 } 
} // SangTao2 
Bài 1.16 Các tam giác vuông cân 
ACM 
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 
 47 
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; 
5 
6 0 3 
1 0 3 
2 1 3 
4 1 2 
4 5 2 
16.50 
 y C 
 A B 
 o x 
T M 
S 
Y 
X V E 
R P 
Q 
 48 
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); 
 49 
 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. 
// C# 
using System; 
using System.IO; 
using System.Collections; 
namespace SangTao2 { 
 class TamGiac { 
 const string fn = "TamGiac.inp"; 
 const string gn = "TamGiac.out"; 
 static public int n, m; // n - so luong HCN; m - so bang 
 static public TG[] c; 
 static public float dt; // tong dien tich 
 static public int[] y; 
 static void Main(string[] args){ 
 Doc(); QSortByx1(0, n - 1); XuLi(); 
 Ghi(); XemKetQua(); 
 Console.WriteLine("\n Fini "); Console.ReadLine(); 
 } 
 static public void Ghi(): tự viết 
 static public void XemKetQua(): tự viết 
 static public void XuLi() { 
 dt = 0F; 
 50 
 int[] s = new int[m]; 
 int[] e = new int[m]; 
 for (int i = 0; i < m; ++i) 
 s[i] = e[i] = int.MinValue; 
 // Duyet cac TG c[i] 
 for (int i = 0; i < n; ++i) { 
 int x2 = c[i].x1+c[i].d; // dau phai cua canh day 
 int sj = BinSearch(c[i].y1); 
 int ej = BinSearch(c[i].y1 + c[i].d); 
 for (int j = sj; j < ej; ++j) { 
 // xet bang j 
 int h = y[j + 1] - y[j]; // do rong cua bang j 
 if (c[i].x1 <= e[j]) { 
 int k = c[i].x1 - (e[j] - h); 
 if (k > 0) dt -= (float)(k * k) / 2; 
 e[j] = Max(e[j], x2); 
 } 
 else { 
 if (e[j] > s[j]) 
 dt += (float)(2*(e[j]-s[j])-h)*h/2; 
 s[j] = c[i].x1; e[j] = x2; 
 } 
 x2 -= h; 
 } // xong bang j 
 } // xong TG i 
 // Tong hop ket qua 
 int m1 = m - 1; 
 for (int j = 0; j < m1; ++j) { 
 int h = y[j+1]-y[j]; // do rong cua bang 
 if (e[j] > s[j]) 
 dt += (float)(2*(e[j]-s[j])-h)* h/2; 
 } 
 static public int Max(int a, int b): tự viết 
 static public void Doc() { 
 int[] v = 
 Array.ConvertAll(((File.ReadAllText(fn))).Split( 
 new char[] { ' ', '\t', '\r', '\n' }, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 int j = 0; n = v[j]; 
 c = new TG[n]; 
 m = 0; 
 y = new int[2 * n]; 
 for (int i = 0; i < n; ++i, j += 3) { 
 Insert(v[j + 2]); Insert(v[j + 2] + v[j + 3]); 
 c[i] = new TG(v[j + 1], v[j + 2], v[j + 3]); 
 } 
 } 
 // Tim nhi phan gia tri v trong y[0..m-1] 
 static public int BinSearch(int v): tự viết 
 // Xen toa do v vao danh sach cac lan y 
 static public void Insert(int v): tự viết 
 // Sap cac TG tang theo x1 
 static public void QSortByx1(int s, int e): tự viết 
 } // TamGiac 
 public struct TG { 
 public int x1, y1, d; 
 51 
 public TG(int dx, int dy, int dd) 
 { x1 = dx; y1 = dy; d = dd; } 
 } 
} // SangTao2