HGMinh95
10-08-2011, 21:08
Trên mặt phẳng toạ độ có N hình chữ nhật, có toạ độ các đỉnh trong khoảng từ 0 tới 30000. Tính diện tích phần mặt phẳng mỗi điểm bị phủ bởi ít nhất 1 hình chữ nhật.
Input: Dòng đầu tiên ghi số N, trong N dòng tiếp theo mỗi dòng ghi 2 cặp số lần lượt là toạ độ điểm trái dưới và phải trên.
Output: Duy nhất 1 số là tổng diện tích phần mặt phẳng bị phủ bởi ít nhất 1 hình chữ nhật.
Giới hạn: N<=10000.
Hướng dẫn:
- Vì các toạ độ đều nguyên, nếu ta chia mặt phẳng thành lưới các ô vuông thì diện tích phần bị phủ bởi các HCN chính là số ô vuông thuộc ít nhất 1 HCN. Như vậy ta chỉ cần đếm với mỗi cột dọc rộng 1 đơn vị có bao nhiêu ô vuông như vậy là được.
- Số ô bị phủ mỗi cột chỉ thay đổi khi các HCN phủ nó thay đổi. Do đó nếu giữa 2 cột i,i+1 không có sự thay đổi về các HCN phủ lên chúng thì số ô vuông bị phủ ở 2 cột này là bằng nhau. Sự thay đổi này chỉ có khi có 1 cạnh của 1 HCN hoàn toàn thuộc trên đường thẳng đứng giữa 2 cột trên.
Từ 2 nhận xét trên ta đi tới thuật toán sau:
- B1: sắp xếp chỉ số vị trí các cạnh thẳng đứng của các HCN theo chiều tăng dần, những cột thuộc giữa 2 chỉ số liên tiếp sẽ có số ô bị phủ bằng nhau, ta chỉ cần đếm lượng này rồi nhân với số lượng cột là được. Do đó chỉ xét 1 cột ngay sau vị trí 1 cạnh là đủ.
- B2: xét các cột từ trái sang phải, nếu lần đầu tiên gặp 1 HCN (gặp cạnh dọc trái của nó) thì thêm đoạn mà nó phủ ở cột tương ứng, nếu đó là cạnh dọc phải của HCN thì loại bỏ đoạn mà nó phủ. Mỗi lần xét 1 cột đếm số lượng ô bị phủ của cột đó.
Cái hướng dẫn trên khó hiểu quá, mọi người giải thích hộ mình nhé!!!
Input: Dòng đầu tiên ghi số N, trong N dòng tiếp theo mỗi dòng ghi 2 cặp số lần lượt là toạ độ điểm trái dưới và phải trên.
Output: Duy nhất 1 số là tổng diện tích phần mặt phẳng bị phủ bởi ít nhất 1 hình chữ nhật.
Giới hạn: N<=10000.
Hướng dẫn:
- Vì các toạ độ đều nguyên, nếu ta chia mặt phẳng thành lưới các ô vuông thì diện tích phần bị phủ bởi các HCN chính là số ô vuông thuộc ít nhất 1 HCN. Như vậy ta chỉ cần đếm với mỗi cột dọc rộng 1 đơn vị có bao nhiêu ô vuông như vậy là được.
- Số ô bị phủ mỗi cột chỉ thay đổi khi các HCN phủ nó thay đổi. Do đó nếu giữa 2 cột i,i+1 không có sự thay đổi về các HCN phủ lên chúng thì số ô vuông bị phủ ở 2 cột này là bằng nhau. Sự thay đổi này chỉ có khi có 1 cạnh của 1 HCN hoàn toàn thuộc trên đường thẳng đứng giữa 2 cột trên.
Từ 2 nhận xét trên ta đi tới thuật toán sau:
- B1: sắp xếp chỉ số vị trí các cạnh thẳng đứng của các HCN theo chiều tăng dần, những cột thuộc giữa 2 chỉ số liên tiếp sẽ có số ô bị phủ bằng nhau, ta chỉ cần đếm lượng này rồi nhân với số lượng cột là được. Do đó chỉ xét 1 cột ngay sau vị trí 1 cạnh là đủ.
- B2: xét các cột từ trái sang phải, nếu lần đầu tiên gặp 1 HCN (gặp cạnh dọc trái của nó) thì thêm đoạn mà nó phủ ở cột tương ứng, nếu đó là cạnh dọc phải của HCN thì loại bỏ đoạn mà nó phủ. Mỗi lần xét 1 cột đếm số lượng ô bị phủ của cột đó.
Cái hướng dẫn trên khó hiểu quá, mọi người giải thích hộ mình nhé!!!