Tam giác có diện tích lớn nhất

Hien_Nguyen · May 11, 2021, 2:35pm

Cho tọa độ 5000 điểm (y, x) là (tung độ, hoành độ) thuộc kiểu int
Làm thế nào để tìm ra 3 đỉnh tam giác có diện tích lớn nhất? Time : 2s

Diện tích thì em dùng tích có hướng. Nhưng 3 vòng for TLE cái chắc, có cách nào khắc phục không ạ?

#include <bits/stdc++.h>
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define maxn 5005

using namespace std;

int n, a, b, c;
ll S, x[maxn], y[maxn], maxS;

ll DienTich(int a, int b, int c){
    return abs((x[b]-x[a]) * (y[c]-y[a]) - (x[c]-x[a]) * (y[b]-y[a]));
}

int main(){
    cin >> n >> S;
    fi(i, 1, n) cin >> x[i] >> y[i];
    fi(i, 1, n)
        fi(j, i+1, n)
            fi(k, j+1, n)
                if (DienTich(i, j, k) > maxS){
                    maxS = DienTich(i, j, k);
                    a = i; b = j; c = k;
                }
    cout << x[a] << ' ' << y[a] << '\n';
    cout << x[b] << ' ' << y[b] << '\n';
    cout << x[c] << ' ' << y[c];
}

tntxtnt · May 11, 2021, 3:51pm

bài này khó :V

diện tích lớn nhất có lẽ phải nằm trên bao lồi (ko biết cách chứng minh :V) nên trước tiên tìm bao lồi của n điểm, O(n log n). Sau đó tìm tam giác lớn nhất trong các điểm thuộc bao lồi này.

cách này lẹ hơn nhưng nếu tất cả các điểm ban đầu nằm trên 1 đường tròn thì cũng như không :V

trên SO có chỉ cách tìm trong O(n^2) trên bao lồi thay vì O(n^3). Đầu tiên phải sort các điểm trên bao lồi theo chiều kim đồng hồ (hay ngược kim đồng hồ cũng được). Bước tìm bao lồi sẽ có thuật toán sắp xếp sẵn các điểm trên bao lồi luôn. Sau đó duyệt 3 vòng for A, B, C trên mảng các điểm đã được sắp xếp này. Duyệt vậy tưởng trâu nhưng ko phải, có cắt bớt chỗ ví dụ khi duyệt C nếu tam giác ABC mới bé hơn tam giác ABC cũ thì ngưng, duyệt B mới. B mới mà ngay tam giác đầu tiên nó bé hơn cũng ngưng. Với A thì phải duyệt hết :V

Hien_Nguyen · May 18, 2021, 10:32am

em cũng thấy code dùng bao lồi rồi, nhưng ông này chỉ có O(n) nên em thử và TH không ra

nitro2 · May 18, 2021, 12:16pm

Đọc bài trên k hiểu lắm, nên tự nghĩ 1 cách tìm bao lồi như sau:

Tìm điểm có tung độ nhỏ nhất, ở đây là A
Từ A, tìm tia hợp với Ox một góc nhỏ nhất. Đây là bài toán tính góc dựa vào vector -> Ở đây tia AC có góc hợp với Ox là nhỏ nhất -> O(n) -> Tìm được C
Từ C tìm tia hợp với AC một góc nhỏ nhất -> ra tia CE
Từ E tìm tia hợp với CE một góc nhỏ nhất -> ra tia EF
…
Lặp lại cho tới khi trở lại điểm A thì có tập hợp bao đóng.

Như vậy thuật toán bao lồi trên cơ bản là O(n^2)
…
Edited: Trong quá trình tìm bao lồi thì tính luôn diện tích tam giác theo tọa độ 3 đỉnh cũng được. Như vậy cuối cùng có kết quả luôn. Ví dụ ở bước 3 thì tìm max của các tam giác có 1 cạnh là AC.
Như vậy sau khi có bao lồi thì cũng có luôn max của tất cả các tam giác có cạnh là cạnh của đa giác bao lồi.

tntxtnt · May 18, 2021, 2:12pm

còn tam giác ko có cạnh là cạnh của bao lồi thì sao :V ví dụ cạnh AE với cạnh nào khác, ở đây bao lồi 5 điểm ít quá lỡ 5000 điểm đều thuộc bao lồi (5000 điểm thuộc 1 đường tròn) thì sao :V

bao lồi có Graham scan O(n log n) nè, bonus sắp xếp các điểm trên bao lồi theo chiều thuận/ngược kim đồng hồ luôn

video giải thích

nitro2 · May 18, 2021, 4:07pm

Thì đằng nào cũng có bao lồi rồi mà
Trường hợp tệ nhất là 5000 điểm đều thuộc bao lồi -> có C(5000,3) = 2 tỷ trường hợp.
Nếu đề mà ra worst case kiểu này thì không thể chạy 2s với những tiên đề đã thảo luận ở trên được.

tntxtnt · May 18, 2021, 5:16pm

thì mới có cái link SO ở trên đó

By first sorting the points / computing the convex hull (in O(n log n) time)
…

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   if A==B: B = (B+1)%n
   if B==C: C = (C+1)%n
   if A==0: break

từ O(n^3) còn O(n^2) nếu các điểm đó đã được sx theo chiều thuận/nghịch kim đồng hồ. 5000 thì O(n^2) 2 giây có lẽ kịp.