[DIS] mọi người giải giúp bài toán này nhé

[real_time]

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]

sao nhiều người đọc thế mà chẳng có ai trả lời giúp một tiếng với

[Mach2]

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]

đâ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.

[Mach2]

À 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]

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ơ.

[Mach2]

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]

nghe có vẻ hợp lý đó bạn viết thử đi mình sẽ cố gắng xem!

[Mach2]

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]

delphi cũng được mà tôi nhận hết! march2 cứ mail đi mail của tôi là loveu4aresion@hotmail.com