Bài tập về đồ họa pascal ! Giúp em với!

[NothingToLost]

Cho n điểm
Bt1 :vẽ 1 hình tròn bao quanh n điểm sao cho diện tích của hình tròn là nhỏ nhất.
Bt2 :vẽ 1 đa giác sao bao quanh n điểm sao cho diện tích của đa giác là nhỏ nhất.

[Master_Baby]

- Thân gửi NoThingToLost

Cho n điểm
Bt1 :vẽ 1 hình tròn bao quanh n điểm sao cho diện tích của hình tròn là nhỏ nhất.

Hề, bài này dễ. Đầu tiên pác tìm 2 điểm nằm ở cực trái. Vẽ đường trung trực của đoạn thẳng có 2 đầu mút là 2 điểm này. Tìm thử xem trên đường trung trực đó có điểm nào thỏa mãn là tâm của đường tròn đó không. (Thỏa mãn <=> khoảng cách từ điểm đó đến 2 mút > khoảng cách từ điểm đó đến các điểm còn lại. Sau đó... vẽ thôi.

Bt2 :vẽ 1 đa giác sao bao quanh n điểm sao cho diện tích của đa giác là nhỏ nhất.

Nếu tui nhớ hông nhầm thì bài này anh iem mình làm rùi mà. Đổi màu nét vẽ. Lấy 4 điểm: 1 điểm cực trên, 1 điểm cực dưới, 1 điểm cực trái, 1 điểm cực phải làm đỉnh 1 đa giác. Tô màu đa giác đó(<> màu các điểm). Những điểm nào không có màu cũ => nằm trong đa giác. Tiếp tục xét các điểm còn lại= cách nối 2 điểm cực với 1 điểm bất kỳ còn lại, đổ màu,... Sau cùng, đổ màu vào đa giác đó (màu đen) và chấm lại các điểm.
- Thân

[NothingToLost]

- Thân gửi NoThingToLost

Đầu tiên pác tìm 2 điểm nằm ở cực trái. Vẽ đường trung trực của đoạn thẳng có 2 đầu mút là 2 điểm này. Tìm thử xem trên đường trung trực đó có điểm nào thỏa mãn là tâm của đường tròn đó không. (Thỏa mãn <=> khoảng cách từ điểm đó đến 2 mút > khoảng cách từ điểm đó đến các điểm còn lại. Sau đó... vẽ thôi.

- Thân

-> thế thử chứng minh bằng toán học đi.Vả lại tìm 2 điểm bất kì ở cực trái à, nếu thế thì sao mà biết để mà tìm được.

[NothingToLost]

-> thế thử chứng minh bằng toán học đi.Vả lại tìm 2 điểm bất kì ở cực trái à, nếu thế thì sao mà biết để mà tìm được.

Ê sao không chứng minh vậy. Chắc là không biết chứ gì.
Gà quá đấy!!!

[Master_Baby]

Hơ hơ, chẳng qua tui ko vào xem nên ko biết thôi... cứ đợi đó....
Nghe nè: không phải 2 điểm bất kỳ ở cực trái, mà là chọn 2 điểm cực. Có hiểu ko? Chọn 1 điểm ở cực trái, loại ra rồi chọn tiếp một cực nữa...
Còn chứng minh toán học, Nothingtolost có xem kỹ ở trên chưa? Lấy tâm nằm trên trung trực => đi qua 2 đầu mút... tiếp theo chỉ là xét xem khoảng cách đã phù hợp chưa mà thôi...

[NothingToLost]

Chọn 1 điểm ở cực trái...

Vô lí ! Làm sao xác định được một điểm cực trái.
Thế hỏi lại điểm cực trái là gì?
Thử đưa cho tui cái code, xem nó như thế nào?
Ở đây không post được hình nên khó hiểu quá!

Lấy tâm nằm trên trung trực => đi qua 2 đầu mút... tiếp theo chỉ là xét xem khoảng cách đã phù hợp chưa mà thôi...

Cái xét khoảng cách, tìm trung điểm thì tui biết nhưng sao mà xét được 1 đường thẳng vuông góc với đường thẳng còn lại.

Mong chỉ giúp cái!

[noname.cpp]

Có thể Master_Baby diễn đạt không đúng.
Thuật toán là thế này :

Tìm ra 2 điểm A và B trong n điểm sao cho khoảng cách giữa 2 điểm này là lớn nhất và gọi khoảng cách này là L.

Gọi I là trung điểm của AB.
1>Nếu khoảng cách từ I đến tất cả các điểm còn lại đều <= L/2 thì đường tròn phải tìm là (I,L/2).

2>Ngược lại ,dựng trung trực của AB ,xuất phát từ I tìm về 2 phía được một điểm O sao cho khoảng cách từ O đến tất cả các điểm còn lại <= OA.Khi đó đường tròn phải tìm là (O,OA)

Có thể chứng minh thuật toán bằng một bài toán hình học nhưng tôi không tiện nêu ra ở đây ,bạn có thể tự làm.

[Master_Baby]

- Thân gửi... mọi người :
Em không nghĩ là tìm 2 điểm có vị trí cách xa nhau nhất, mà em nghĩ là tìm 2 vị trí ở xa nhất bên trái (hoặc bên phải) so với các điểm khác (tức là ở cực trái). Em cũng không nghĩ chọn 2 điểm cách xa nhất đã là ổn. VD như hình:

(với điểm C nằm ở trung trực đoạn AB, thỏa mãn AB/2<AC<AB). Vì C nằm cách AB xa nhất => phải vẽ đường tròn hoặc đi qua C hoặc chứa C. Ta cũng dễ dàng tìm ra được các điểm D nằm gần đường tròn (ko thuộc trung trực AB) thỏa mãn CD<AB, D không thuộc đường tròn ngoại tiếp ABC.
- Thân

[NothingToLost]

To noname.cpp:
Trước đây em cũng đã nghĩ theo cách của anh rùi . Nhưng mà đúng như Master_Baby chứng minh cách đó không hoàn toàn tối ưu.
TO Master_Baby:
Ông thử post hình lên tui xem nào. Có lẽ ông cũng nên chứng minh thuật toán của ông là tối ưu nhất xem sao .

[bete]

Tui đọc cách giải của MasterBaby nhưng không rõ lắm
=>MasterBaby có thể vẽ hình được không ?

Bạn Aiza đã từng post cách giải ở http://www.ddth.com/showthread.php?t...ight=tr%C3%B2n

-thân