View Full Version : [DIS] mọi người giải giúp bài toán này nhé
real_time
11-10-2002, 10:03
cho n đường thẳng trên hệ toạ độ (xoy) các đường thẳng này là bất kỳ không có phương trình hay gì gì đâu hết đâu nhé.
Yêu cầu tô màu tất cả các tam giác hình thành bởi các đường thẳng đã cho.
ghi chú: tam giác được tô màu thì phải không chứa bất cư hình con gì nằm bên trong nó.
real_time
17-10-2002, 16:34
sao nhiều người đọc thế mà chẳng có ai trả lời giúp một tiếng với
Khó wé!!!
Tui chỉ nghĩ ra cách "ngu ngu" đi duyệt từng cặp điểm tạo bởi các giao điểm của đường thẳng cắt nhau thui, nhưng mà chưa viết code thử nên ko biết có khả thi ko?
Bài khó wé mờ, tui đọc mấy lần rồi mà vẫn không thấy có ý tưởng gì hay cả? Mà bạn cần bài toán trên để làm gì nhỉ? Cho tui tò mò một tí?
real_time
26-10-2002, 14:25
đây là một dạng toán để áp dụng thuật toán tô màu mà sử dụng thuật toán tô màu thì có thể sử dụng nhiều vào để tô màu bản đồ. Chẳng hạn bạn có một bản đồ có n nước nhé hãy tô màu sao cho những nước có cùng biên giới là không cùng màu nhau chẳng hạn.
À thế mà tôi cứ tưởng là chỉ những tam giác mới cần được tô màu thôi chứ? Bởi vì đường thẳng cắt nhau thì tạo ra nhiều hình lắm, tam giác, tứ giác,... Nếu phải chọn tam giác mới tô thì khó thật, phải chọn lựa, duyệt tùm lum, còn chỉ cần tô một vùng khép kín thì không quá phức tạp lắm. Hoá ra là bài toán của bạn là dùng để vẽ bản đồ à? Như vậy thì ta có thể dùng một số giải thuật Floodfill là được rồi.
real_time
29-10-2002, 13:36
cơ bản là tô màu hình kín. còn trong bài này mình bị bắt buộc phải tô tam giác cơ.
Tôi nghĩ đại khái ý tưởng là như vầy...
- Tìm các điểm giao nhau giữa các đoạn thẳng và lập thành một tập điểm mới.
- Kiểm tra từng 3 điểm một trong tập điểm mới tạo này, nếu có 3 điểm nào đó thoả đồng thời các điều kiện: không cùng nằm trên cùng một đường thẳng, 3 cặp điểm đôi một nằm trên cùng một đường thẳng, giữa một cặp điểm trong 3 cặp này không có một điểm giao nhau nào khác. Nếu 3 trường hợp này thoả thì tạo tam giác.
Tôi nghĩ cũng không có gì phức tạp lắm, chỉ cần một số kiến thức hình học giải tích thôi. Bạn có cần chương trình không? Nếu cần thì tôi sẽ viết thử cho bạn.
real_time
30-10-2002, 20:13
nghe có vẻ hợp lý đó bạn viết thử đi mình sẽ cố gắng xem!
Tôi viết xong rồi, nói chung là thuật toán tương đối ổn nhưng mà nó hơi bị chậm, có lẽ tại tôi chưa tối ưu vài cái thủ tục giải tích. Real_time giải được chưa? Tôi viết trên Delphi nên không tiện gửi lên. Real_time có cần thì cho tôi email tôi sẽ gửi cho.
real_time
03-11-2002, 12:36
delphi cũng được mà tôi nhận hết! march2 cứ mail đi mail của tôi là loveu4aresion@hotmail.com
real_time đợi tôi thêm vài ngày để sửa một tí. Mấy bữa nay tôi thi nên không coi lại nó được.
real_time
07-11-2002, 10:29
được thôi lúc nào bạn gửi lên cũng được mà
He he !
Bài này tụi tôi làm hơi bị nhanh đấy ! Không có thuật toán gì sất ! Chắc bạn cũng biết chỉ cần 4 màu có thể tô tất cả các miền của bản đồ rồi chứ? Cứ gặp miền nào chưa được tô thì tô luôn tất nhiên có kiểm tra điều kiện không có miền chung cạnh cùng màu.
Quan trọng là xác định miền thôi, bạn nói đường thẳng không có phương trình thì làm sao xác định được miền ?
real_time
11-11-2002, 20:53
chính vì lẽ đó mình mới đau đầu chứ còn nếu có phương trình đường thẳng thì mình chi khoanh vùng là xong mà!
có 2 điểm là có đường thẳng thui? real_time làm xong bài này chưa? code tui hình như có chỗ bị sai đó, ko biết real_time có thấy ko?
real_time
20-11-2002, 09:54
mình hiểu rồi march2 ạ nói chung là dùng theo cách đó có lẽ là hợp lý. Còn lỗi thì để đó từ từ giải quyết.
Tôi thấy bài của bạn real_time đưa ra rất hay.Mach2 có thể gửi Code cho tôi với được không .Tungtd979@yahô.com
dark_life2
23-11-2002, 20:42
ê sao lại lôi bài toán này ra vậy khó wá không giải được àh
real_time
25-11-2002, 13:02
hê march2 đã gửi cho em lời giải rồi nếu anh muốn hôm nào em mang đến cho.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.