MTKC spoj – Khoảng cách
Link submit: http://www.spoj.com/THPTCBT/problems/MTKC/ 1. Đề bài MTKC spoj Trước cửa nhà Mr Bill có một cái hồ rất rộng. Giữa hồ có một hòn đảo nhỏ. Một lần Mr Bill nảy ra ý định bắc một cái cầu từ cửa nhà mình đến đảo giữa hồ để kinh doanh du lịch. Một vấn đề khá hóc búa đối ...
Link submit: http://www.spoj.com/THPTCBT/problems/MTKC/
1. Đề bài MTKC spoj
Trước cửa nhà Mr Bill có một cái hồ rất rộng. Giữa hồ có một hòn đảo nhỏ. Một lần Mr Bill nảy ra ý định bắc một cái cầu từ cửa nhà mình đến đảo giữa hồ để kinh doanh du lịch. Một vấn đề khá hóc búa đối với Mr Bill là làm thế nào xác định được khoảng cách từ nhà mình đển đảo giữa hồ?.
Có thể mô tả đảo giữa hồ như là một đa giác lồi còn nhà của Mr Bill như là một điểm nằm ngoài đa giác đó trên mặt phẳng toạ độ. Bạn hãy lập trình giúp Mr Bill tính khoảng cách nhỏ nhất từ nhà mình đến đảo.
Input: Vào từ file văn bản BILL.INP
- Dòng đầu tiên ghi N là số đỉnh của đa giác (N≤1000)
- Dòng thứ hai ghi toạ độ của điểm được xem như là nhà của Mr Bill
- Tiếp theo là N dòng, mỗi dòng liệt kê toạ độ của một đỉnh của đa giác. Các đỉnh của đa giác được liệt kê ngược theo chiều kim đồng hồ.
Output: Ghi ra file BILL.OUT một số thực duy nhất là khoảng cách từ nhà của Mr Bill đến đảo giữa hồ (giữ lại 4 chữ số phần thập phân)
Ví dụ:
| BILL.INP | BILL.OUT |
| 3 0 0 2 0 0 2 2 2 | 1.4142 |
2. Lời giải MTKC spoj – Khoảng cách
– Gọi kết quả bài toán là res
– Đầu tiên tính khoảng cách ngắn nhất từ nhà Bill đến các đỉnh của đa giác, res:=min(res,khoangcach(bill,p[i]));
– Tuy nhiên khoảng cách từ đỉnh đa giác tới nhà bill không phải là khoảng cách ngắn nhất từ bill đến đa giác, vì thế ta phải tìm khoảng cách ngắn nhất từ Bill đến từng cạnh của đa giác.
Cụ thể như sau:
– Ta tìm đường thẳng vuông góc với cạnh của đa giác và đi qua nhà Bill, sau đó tìm tọa độ giao điểm giữa đường thẳng đó và cạnh đa giác tương ứng, Sau đó kiểm tra xem tọa độ giao điểm đó có nằm trên cạnh đa giác hay không? nếu có thì tính khoảng cách từ tọa độ giao điểm đến nhà Bill và cập nhật kết quả.
3. Code tham khảo MTKC SPOJ – Khoảng cách
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | const fi='bill.inp'; fo='bill.out'; nmax=1500; esp=0.00001; type data=longint; point=record x,y:real; end; polygon=array[0..nmax+1] of point; var f:text; P:polygon; M:point; n:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); readln(f,m.x,m.y); for i:=1 to n do readln(f,p[i].x,p[i].y); close(f); end; function KC(a,b:point):real; begin exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))); end; procedure ptdt(p1,p2:point; var a,b,c:real); begin a:=p2.y-p1.y; b:=p1.x-p2.x; c:=(p2.x*p1.y-p1.x*p2.y); end; function equal(a,b:real):boolean; begin if abs(a-b)<esp then exit(true); exit(false); end; function pthdgd(var i:point; a1,b1,c1,a2,b2,c2:real):data; var d,dx,dy:real; begin d:=a1*b2-a2*b1; dx:=c2*b1-c1*b2; dy:=a1*c2-a2*c1; if equal(d,0) then exit(0); i.x:=dx/d; i.y:=-dy/d; exit(1); end; function min(a,b:real):real; begin if a<b then exit(a); exit(b); end; function max(a,b:real):real; begin if a>b then exit(a); exit(b); end; function ccw(a,b,M:point):data; var k:real; begin k:=(b.x-a.x)*(m.y-b.y)-(m.x-b.x)*(b.y-a.y); if equal(k,0) then exit(0) else if k>0 then exit(1); exit(-1); end; function Poinln(m,a,b:point):boolean; begin exit( (ccw(a,b,m)=0) and (min(a.x,b.x)<=m.x) and (m.x<=max(a.x,b.x)) and (min(a.y,b.y)<=m.y) and (m.y<=max(a.y,b.y))); end; procedure xuli; var i,j,k:data; A,B,Z:point; res,tmp,hsa,hsb,hsc,d,dx,dy:real; begin // KC tu M den point res:=kc(p[1],M); for i:=2 to n do res:=min(res,kc(p[i],M)); p[n+1]:=p[1]; for i:=1 to n do begin ptdt(p[i],p[i+1],hsa,hsb,hsc); k:=pthdgd(z,hsa,hsb,hsc,-hsb,hsa,-(-hsb*m.x+hsa*m.y)); if k=0 then continue; // neu trung nhau hoac song song thi bo qua if PoInLn(z,p[i],p[i+1]) then res:=min(kc(z,m),res); end; assign(f,fo); rewrite(f); writeln(f,res:0:4); close(f); end; begin docfile; xuli; end. |
