Chuyên đề: Kĩ thuật bao lồi (Convex Hull Trick) PHẦN I: MỞ ĐẦU Từ tốn Batch Scheduling kì thi IOI 2002, kĩ thuật bao lồi đưa rộng rãi vào thi lập trình Nhưng kĩ thuật bao lồi biết đến nhiều từ toán Acquire bảng Gold USACO năm 2008 Kĩ thuật bao lồi kĩ thuật (hoặc cấu trúc liệu) dùng để xác định cực trị tập hàm tuyến tính giá trị biến độc lập Nó khơng giống thuật tốn bao lồi hình học, có tên kĩ thuật có phần tạo đường bao đường lồi để hình thành bao lồi tập điểm Kĩ thuật dùng để cải tiến tốn quy hoạch động thời gian xuống cịn , chí số trường hợp cịn xuống cho lớp tốn Tơi nhận thấy kĩ thuật lạ, thú vị có tài liệu nó, nên định tìm hiểu viết chuyên đề: “Kĩ thuật bao lồi (Convex Hull Trick) ứng dụng” Chuyên đề: Kĩ thuật bao lồi (Convex Hull Trick) PHẦN II: NỘI DUNG I KĨ THUẬT BAO LỒI (CONVEX HULL TRICK) Bài toán Cho tập n đường thẳng điểm trục : Tìm thỏa mãn: - Dữ liệu vào: Cho file CHT.INP.* o Dòng số nguyên , số đường thẳng dòng dòng chứa hai số thực hệ số phương trình đường o thẳng o Dòng chứa số nguyên , số lượng truy vấn dòng dòng chứa số thực o - Dữ liệu ra: In file CHT.OUT o Mỗi dòng số thực giá trị thỏa mãn - Ví dụ: - CHT.INP 0.17 2.67 13 0.5 0.8 -2 Giới hạn: CHT.OUT o o 1.1 Phân tích Với điểm , duyệt qua tất đường thẳng tập ta tính thời gian Do tổng thời gian để tìm tất điểm Vấn đề đặt cải tiến thuật tốn hay khơng? Đầu tiên ta xét ví dụ với tập sau: Chuyên đề: Kĩ thuật bao lồi (Convex Hull Trick) Với điểm , giá trị nhỏ tương ứng điểm thỏa mãn điểm thuộc phần gạch đỏ hình Phần gạch đỏ hình tập đoạn thẳng chứa tất điểm cực tiểu cho giá trị Phần gạch đỏ tạo thành đường bao lồi tập điểm nên kĩ thuật gọi kĩ thuật bao lồi Từ viết tắt kĩ thuật bao lồi CHT Thuật tốn tốn có hai bước chính: Bước 1: Xây dựng bao lồi đường thẳng Bước 2: Thực truy vấn bao lồi tìm bước a) Thực bước 1: Dựa hình vẽ, ta thấy đường thẳng dư thừa (tung điểm điểm có hồnh độ đường thẳng ln lớn tung độ điểm có hồnh độ đường thẳng khác ) Biểu diễn bao lồi ví dụ tập đoạn: đường thẳng tương ứng là: Ta nhận thấy : Bao lồi tập đường thẳng cho trước biểu diễn m đoạn đường thẳng tương ứng với đoạn Hơn nữa, ta tìm biểu diễn thời gian Giả mã: Để đơn giản ta giả sử khơng có hai đường thẳng song song Ta có giả mã thuật tốn tìm bao lồi Void { FindHull ; Sort ; // xếp theo hệ số góc giảm dần Stack ; // khởi tạo ngăn xếp rỗng Push; // Đẩy đường thẳng vào ngăn xếp ; ; // mảng lưu đường thẳng thuộc bao lồi Chuyên đề: Kĩ thuật bao lồi (Convex Hull Trick) For { d top(); //lấy phần tử ngăn xếp mà không xóa find_intersection_x (d, di);//tìm hồnh độ giao điểm đường thẳng d di // loại bỏ đường thẳng dư thừa While (left()) { Pop(); //loại bỏ đường thẳng d d dư thừa .top(); ; } push(); ; ; ; } } Nhận xét : Nếu đường thẳng lấy khỏi Stack, khơng kiểm tra lại Vì vậy, thời gian thuật tốn tìm bao lồi chủ yếu dành để xếp đường thẳng theo hệ số góc Độ phức tạp: b) Thực bước 2: Tìm tất điểm thỏa mãn Giả sử tìm bao lồi , với điểm trục hồnh, sử dụng tìm kiếm nhị phân để tìm cho Ta tính thời gian Nên để tìm điểm ta thời gian Giả mã: Query(); { FindHull(; For { ; Return ; } } ; { If return Else { } If return ; Else if return interval_search Else return interval_search; } Vậy tổng thời gian toán 1.2 Cài đặt: Chuyên đề: Kĩ thuật bao lồi (Convex Hull Trick) #include #define MAX_SIZE 1000000 #define INFTY 100000000 using namespace std; typedef struct{ //cấu trúc đường thẳng y = ax+b double a; double b; } double_pair; stack S; // double_pair D[MAX_SIZE]; // có hai tham số a b double_pair I[MAX_SIZE]; // double Q[MAX_SIZE]; // int ALines[MAX_SIZE];// int n, m,q; long long A[MAX_SIZE]; long long B[MAX_SIZE]; stack mảng lưu đường thẳng, đường thẳng mảng đoạn thuộc interval mảng điểm thuộc truy vấn tập đường thẳng chứa interval void readinput(){ freopen("CHT.INP","r",stdin); freopen("CHT.out","w",stdout); cin >> n; for(int i = ; i < n; i++) cin>>D[i].a>>D[i].b; cin>>q;// số lượng truy vấn for(int i = ; i < q; i++) cin>> Q[i]; } // tìm hồnh độ giao điểm dx dy double find_intersection_x(int x, int y) { return ((double)(D[y].b-D[x].b))/((double)(D[x].a - D[y].a)); } //sắp xếp hệ số góc giảm dần bool slope_compare(double_pair d1, double_pair d2) { return ((d1.a > d2.a) || (d1.a == d2.a && d1.bH[i]>>C[i]; v[i].clear(); } for (int i=0; i>a>>b; a ; b ; v[a].push_back(b); v[b].push_back(a); } go0(0, -1, 0); gh = *max_element(h, h + n); for (int i=0; i= 0) up.pop_back(); while (dn.size() > && area2(dn[dn.size()-2], dn.back(), pts[i]) = 1; i ) pts.push_back(up[i]); } int pointer[2]; //Lưu trữ đường tốt từ query trước vector M[2]; //Hệ số góc đường bao lồi vector B[2]; //Giá trị B đường thẳng Mx+B //Trả lại True đường thẳng l1 l3 tốt l2 bool bad(int l1,int l2,int l3,bool f) { /* hoành độ giao điểm l1 l2 là: (b1-b2)/(m2-m1) hoành độ giao điểm l1 l3 là: (b1-b3)/(m3-m1) */ return (B[f][l3]-B[f] [l1])*(M[f][l1]-M[f][l2])=3&&bad(M[f].size()3,M[f].size()-2,M[f].size()-1,f)) { M[f].erase(M[f].end()-2); B[f].erase(B[f].end()-2); } } //Trả tọa độ y nhỏ giao điểm đường thẳng đứng với cách canh bao lồi long double Query(long double x,bool f) { //Nếu ta loại bỏ đường thẳng tốt cho truy vấn trước //thì đường thẳng vừa chèn tốt cho truy vấn if (pointer[f]>=M[f].size()) pointer[f]=M[f].size()-1; //Bất kỳ đường thẳng tốt phải nằm bên phải giá trị truy vấn khơng giảm while (pointer[f]t; while(t ) { M[0].clear(); M[1].clear(); B[0].clear(); B[1].clear(); pointer[0]=pointer[1]=0; cin>>n; vector v; v.clear(); for(i=0;i>X[i]; cin>>Y[i]; arr[i]=MP(X[i],Y[i]); PT pt(X[i],Y[i]); v.PB(pt); } ConvexHull(v); if(v.size()==n) { cout