kết quả từ 1 tới 10 trên 10

giúp tiếp bài này với các bạn nhé

  1. #1
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp tiếp bài này với các bạn nhé

    Bài 3:
    Mình chưa nghĩ đc cách tốt hơn là duyệt hết. Lưu ý là bạn cần khai báo double (hoặc mình nghi là phải so sánh chuỗi) để so sánh số. Vì chiều dài tối đa của chuỗi là 150, double hoàn toàn chứa đc số này nhé.

    Bài 4:
    Mình ko rõ giới hạn của (xi, yi) thế nào, nhưng với N < 256 thì duyệt hết O(N^3) cỡ 2^24 vẫn chạy đc.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: giúp tiếp bài này với các bạn nhé

    bài 4
    đề họ chưa cho kĩ nên cũng ko rõ.theo bạn ý tưởng của bài toán này sẽ như thế nào ak.có phải mình duyệt rồi ktra xem có tồn tạo các tam giac hay không rồi tìm tam giác lớn nhất ko bạn.mong bạn giúp

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp tiếp bài này với các bạn nhé

    Trích Nguyên văn bởi tuonglong Xem bài viết
    bài 4
    đề họ chưa cho kĩ nên cũng ko rõ.theo bạn ý tưởng của bài toán này sẽ như thế nào ak.có phải mình duyệt rồi ktra xem có tồn tạo các tam giac hay không rồi tìm tam giác lớn nhất ko bạn.mong bạn giúp
    Bạn có thể thử trường hợp 3 điểm thẳng hàng rồi tính diện tích. Mình nghĩ nó có thể bằng 0.

  6. #5
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: giúp tiếp bài này với các bạn nhé

    xin nốt code câu 4 luôn bạn ơi,..mù giải thuật mấy dạng này.những dạng sắp xếp,còn mò mẫn được chứ mấy bài mình gửi lên chẳng tìm dk cách giải nào luôn.mình xin code rồi học lại may chăng hiểu....

  7. Đã cảm ơn tuonglong:


  8. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp tiếp bài này với các bạn nhé

    Code của bài 4 thì chỉ vét cạn thôi, đại khái thế này nhé.
    Mã:
    type arr = array[1..256] of double;
    var x, y : arr;
        n, i, j, k, max_i, max_j, max_k : integer;
        max_area, area : double;
        
    BEGIN
    	
    	// read data
    	
        max_area := -1;
        for i := 1 to n - 2 do
            for j := i + 1 to n - 1 do
                for k := j + 1 to n do
                    begin
                        area := abs(x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j]));
                        if (max_area < area) then
                            begin
                                max_area := area;
                                max_i := i;
                                max_j := j;
                                max_k := k;
                            end;
                    end;
        writeln(max_i, ' ', max_j, ' ', max_k);
        writeln(max_area/2 :0:1);
    END.

  9. Đã cảm ơn tengiday:


  10. #7
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: giúp tiếp bài này với các bạn nhé

    bạn cho mình hỏi với,vì sao mình không thấy bạn sử các công thức trong để để tinh toán vậy,

  11. Đã cảm ơn tuonglong:


  12. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp tiếp bài này với các bạn nhé

    - Công thức trong đề đòi hỏi phải dùng sqrt để tính độ dài. Vì sqrt rất tốn tài nguyên tính toán nên ít programmers nào thích dùng. Ngược lại, để tính diện tích tam giác, bạn có thể dùng kiến thức của lớp 10 hay 11, kết quả là 1/2 chiều dài của cross product của 2 vectors AB và AC. Cách tính khôn khéo sẽ dùng determinant của ma trận nên ko liên quan gì tới sqrt cả.
    - Ko riêng gì diện tích tam giác, với đa giác có tọa độ nguyên bất kỳ thì diện tích sẽ luôn luôn là số nguyên hoặc một nửa số nguyên, ko có ngoại lệ nhé. :-)

    Thật ra, bài 4 này mình có cách giải khác rồi. Chỉ là nó cần kỹ thuật lập trính tương đối một tí. Thuật toán sẽ có độ phức tạp là O(n log n), HUGE improvement nhé bạn; n có thể tới 10^5 hay 10^6 luôn. Nếu bạn biết về bài toán convex hull (bao lồi) thì có thể nghĩ theo cách này.

  13. Đã cảm ơn tengiday:


  14. #9
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: giúp tiếp bài này với các bạn nhé

    area := abs(x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j]));
    if (max_area < area) then
    BẠN GIẢI THÍCH CÔNG THỨC NÀY CHO MÌNH VỚI
    THẬT SỰ BÊN TOÁN NHẤT LÀ HÌNH MÌNH QUÁ YẾU NÊN KO HIỂU.
    NẾU LÀM BẰNG KĨ THUẬT LẬP TRÌNH THÌ MAY RA CÒN BIẾT CHỨ TOÁN LÀ MÙ TỊCH

  15. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp tiếp bài này với các bạn nhé

    Cái này là bên toán rồi. Bạn tìm đọc sách là có ngay. Nó liên quan tới determinant của ma trận, cross product của 2 vectors. Xem link sau nhé:
    HTML Code:
    https://math.stackexchange.com/questions/516219/finding-out-the-area-of-a-triangle-if-the-coordinates-of-the-three-vertices-are