Tính chu vi và diện tích hình chữ nhật giao nhau?

Question

Tôi đã tìm kiếm rất nhiều, nhưng tôi không tìm thấy câu trả lời phù hợp cho trường hợp này. Chúng tôi có một số hình chữ nhật nằm ngang hoặc dọc. Chúng có thể được đặt trên trang một cách ngẫu nhiên. Chúng có thể chồng chéo hoặc có một cạnh chung hoặc tách biệt với nhau. Tôi muốn tìm một thuật toán với O (nlogn) có thể tìm thấy chu vi và diện tích của các hình chữ nhật này. Những hình ảnh này có thể làm cho vấn đề rõ ràng.

Tôi nghĩ rằng cây khoảng cách có thể hữu ích, nhưng tôi không chắc chắn như thế nào.

Answer 1

Có thể thực hiện bằng thuật toán quét dòng quét.

Chúng tôi sẽ quét một dòng tưởng tượng từ trái sang phải. Chúng ta sẽ nhận thấy cách giao nhau giữa đường thẳng và tập hợp các hình chữ nhật đại diện cho một khoảng thời gian, và nó thay đổi khi chúng ta gặp phải cạnh trái hoặc phải của hình chữ nhật.

Hãy nói rằng ngã tư không thay đổi giữa x phối x1 và x2. Sau đó, nếu chiều dài của ngã tư sau khi x1 là L, dòng sẽ quét một khu vực bằng (x2 - x1) * L, bằng cách quét từ x1 để x2.

Ví dụ, bạn có thể nhìn vào x1 như dòng màu xanh bên trái, và x1 như dòng màu xanh ngay trên hình ảnh sau đây (mà tôi đã đánh cắp từ bạn và sửa đổi một chút :)):

Phải rõ ràng rằng giao lộ của đường quét của chúng tôi không thay đổi giữa các điểm đó. Tuy nhiên, giao điểm màu xanh là khá khác với giao điểm màu đỏ.

Chúng tôi sẽ cần một cấu trúc dữ liệu với các hoạt động:

insert_interval(y1, y2); 
get_total_length(); 

Những có thể dễ dàng thực hiện với một cây phân khúc, vì vậy tôi sẽ không đi vào chi tiết bây giờ.

Bây giờ, thuật toán sẽ đi như thế này:

1. Mang tất cả các phân đoạn dọc và sắp xếp chúng theo tọa độ x của họ.
2. Đối với mỗi x có liên quan phối hợp (chỉ có những người xuất hiện như cạnh của hình chữ nhật rất quan trọng):
   • Hãy x1 là x có liên quan trước đó, phối hợp.
   • Cho x2 là tọa độ x có liên quan hiện tại.
   • Cho L là độ dài được cung cấp bởi cấu trúc dữ liệu của chúng tôi.
   • Thêm (x2 - x1) * L vào tổng diện tích.
   • Xóa tất cả bên phải cạnh bằng x = x2 phân đoạn từ cấu trúc dữ liệu.
   • Thêm tất cả bên trái cạnh với phân đoạn x = x2 vào cấu trúc dữ liệu.

By trái và đúng Ý tôi là các mặt của một hình chữ nhật.

Ý tưởng này chỉ được đưa ra để tính toán diện tích, tuy nhiên, bạn có thể sửa đổi nó để tính toán chu vi. Về cơ bản bạn sẽ muốn biết sự khác biệt giữa độ dài của giao lộ trước và sau khi nó thay đổi ở một số tọa độ x.

Độ phức tạp của thuật toán là O (N log N) (mặc dù nó phụ thuộc vào phạm vi giá trị bạn có thể nhận được làm đầu vào, điều này dễ dàng được xử lý).

Bạn có thể tìm thêm thông tin về chủ đề rộng của thuật toán quét dòng trên TopCoder.

Bạn có thể đọc về các cách khác nhau để sử dụng cây phân đoạn trên PEG judge wiki.

Đây là triển khai thuật toán (thực sự cũ) của tôi như một giải pháp cho SPOJ problem NKMARS: implementation.

Answer 2

Sau đây là giải pháp O (N2).

int area = 0; 
FOR(triange=0->N) 
{ 
    Area = area trianlges[triangle]; 
    FOR(int j = triangle+1 -> N) 
    { 
     area-= inter(triangle , j) 
    } 
} 
return area; 

int inter(tri a,tri b) 
{ 
    if ((min(a.highY ,b.highY) > max(a.lowerY, b.lowerY)) && (min(a.highX ,b.highX) > max(a.lowerX, b.lowerX))) 
    return (min(a.highY ,b.highY) - max(a.lowerY, b.lowerY)) * (min(a.highX ,b.highX) - max(a.lowerX, b.lowerX)) 

    else return 0; 
}