System 248817F - tacongnam/DylanHarris GitHub Wiki

• Problem: CODEFORCES - System 248817F
• Tag: Convex Hull Trick - CHT
• Name: Bao lồi (Convex Hull Trick)
• Introduction:
  Time limit per test: 0.5 second
  Memory limit per test: 256 megabytes
  Input: standard input
  Output: standard output
  

Table of Contents Content: Dữ liệu Kết quả Ví dụ Solution Code

Cho một tập n đường thẳng D=(d[1],d[2],...,d[n]) trong đó (d[i]):y =a[i]*x+b[i] với a[i]≥0 và k điểm trên trục Ox: p[1],p[2],...,p[k]. Tìm q[1],q[2],...,q[k] trong đó q[i] thỏa mãn: q[i] = min (a[i]∗p[i]+b[i]) với 1≤i≤n

Dòng đầu tiên chứa 1 số nguyên n là số đường thẳng. (n≤10^6)

n dòng tiếp theo mỗi dòng chứa hai số thực a[i], b[i] là hệ số của đường thẳng (0≤a[i]≤10^5, −10^5≤b[i]≤10[5], a[i], b[i] có tối đa 8 chữ số phần thập phân)

Dòng tiếp theo chứa 1 số nguyên k, là số lượng truy vấn. (k≤10^6)

k dòng tiếp theo mỗi dòng chứa một số thực p[i] (−10^7≤p[i]≤10^7, p[i] có tối đa 8 chữ số phần thập phân)

Dòng đầu tiên đưa ra 1 số nguyên s số giao điểm giữa hai đường thẳng nằm trên bao lồi (s≤n)

Dòng tiếp theo in ra s số thực ans[i], là toạ độ x của các giao điểm nằm trên bao lồi (ans[i] có tối đa 8 chữ số phần thập phân)

k dòng tiếp theo, mỗi dòng chứa một số thực là giá trị q[i] thỏa mãn (q[i] có tối đa 8 chữ số phần thập phân)

Input:

 4
 0.17 2.67
 1 3
 0.5 2
 0.8 4
 4
 -2
 2
 4
 0

Output:

 2
 -2.00000000 2.03030303 
 1.00000000
 3.00000000
 3.35000000
 2.00000000

Sử dụng kỹ thuật Bao lồi (Convex Hull Trick)

CLCSystem-248817F-Deque.cpp