[OLP] Bài toán động đất – OLP tin học 2012 khối siêu cúp

Tháng Mười Một 4, 2013 nguyenvanquan7826 TT Spoj Leave a response

Bài 3: Động đất
Hạn chế thời gian cho mỗi test: 1 giây.
Bên bờ dòng sông Chanh có N hộ dân cư đang sinh sống. Khu vực dân cư này đang thường xuyên hứng chịu nhiều trận động đất với cường độ khác nhau. Thông tin về một trận động đất Q bao gồm một bộ ba số nguyên (x, y, f), trong đó:

– (x, y) là vị trí tâm chấn của trận động đất Q;
– f là cường độ trận động đất Q đo được tại tâm chấn (x,y).

Một hộ dân cư nằm tại vị trí (x’, y’) được cho là chịu ảnh hưởng của một trận động đất Q = (x, y, f) nếu như: sqrt{(x-x')^{2}+(y-y')^{2}} leqslant f^2

Trong vòng một tháng qua, trung tâm theo dõi động đất đã phát hiện có tất cả P trận động đất xảy ra ở khu vực dòng sông Chanh. Một hộ dân cư được cho là chịu ảnh hưởng nặng từ các trận động đất nếu như nó chịu ảnh hưởng của ít nhất K trận động đất trong số P trận động  đất trên. Để đánh giá mức độ ảnh hưởng của các trận động đất đối với khu vực dân cư bên bờ dòng sông Chanh, chính quyền địa phương  cần đếm số lượng hộ dân cư chịu ảnh hưởng nặng từ các trận động đất trên.

Yêu cầu: Cho biết thông tin về các trận động đất và vị trí của các hộ dân cư, hãy tính số lượng hộ dân cư chịu ảnh hưởng nặng từ các trận động đất đó.
Dữ liệu: Vào từ file văn bản EQ.INP gồm N+P+1 dòng:

– Dòng đầu chứa 3 số nguyên dương N, P, K (N ≤ 500000, P ≤ 5000);
– N dòng tiếp theo chứa thông tin tọa độ của N hộ dân cư. Dòng thứ i trong số N dòng này chứa 2 số nguyên xi , yi là tọa độ của hộ dân cư thứ i (0 ≤ xi ≤ 10 6 , 0 ≤ yi ≤ 100).
– P dòng tiếp theo chứa thông tin về P trận động đất. Dòng thứ i trong số P dòng này chứa 3 số nguyên xi , yi , fi là thông tin về trận động đất thứ i.

Kết quả: Đưa ra file văn bản EQ.OUT một số nguyên là số hộ dân cư chịu ảnh hưởng nặng từ các trận động đất.

động đất - siêu cúp Olympic 2012
==========

Thực ra mình cũng đã đi tìm lời giải của bài toán nhưng chưa thấy trang nào viết. Mình cùng một số anh em đã làm theo giải thuật dưới đây, tất nhiên là chưa tối ưu, rất mong các bạn chia sẻ để có thể làm bài này một cách tốt hơn.

Trước tiên chúng ta sẽ điểm qua cách dễ nhất mà ai cũng có thể nhìn thấy đó là xét từng căn nhà, với mỗi căn nhà ta sẽ sét với P trận động đất, nếu nó chịu tác động thì tăng count (biến đêm số trận động đất) lên 1 hoặc xét từng trận động đất, với mỗi trận lại xét N căn nhà. Cuối cùng ta chỉ việc đếm xem có bao nhiêu căn nhà chịu ảnh hưởng của k trận trở lên. Vậy là xong con ong @@
Tuy nhiên các bạn có thể thấy dữ liệu của chúng ta với N <= 500.000 và P <= 5.000 là quá lớn không thể thực hiện mỗi test trong 1 giây. Và chúng ta sẽ tìm hiểu cách tốt hơn một chút (không rõ có phải là cách tốt nhất chưa). =))

Trước tiên chúng ta thấy muốn giải được nó chúng ta sẽ tìm các điểm mà chịu tác động của các trận động đất, việc tiếp theo chỉ là đếm và so sánh đưa ra điểm nào bị chịu từ k trận trở lên. Một điểm quan trọng chúng ta chú ý là y<=100. Vậy ta sẽ hướng sự chú ý vào nó.
Chúng ta để ý rằng với mỗi trận động đất mức ảnh hưởng của nó là 1 hình tròn tâm (x, y) bán kính là f^2. Mỗi đường thẳng y = a (0 <= a <= 100) thì ứng với mỗi trận động đất nếu tác động đến nó sẽ là 1 khoảng (1 đoạn thẳng) và ta cần xác định đoạn thẳng đó, tiếp theo là xác định các hộ dân nằm trong nó và tăng biến đếm của nó lên. Từ đây ta đưa bài toán về 2 bài toán con:
1. Xác định các đoạn thẳng cắt bỏi các đường tròn tạo ra từ trận động đất và các đường thẳng y = a (chuẩn bị dữ liệu).
2. Với mỗi đoạn thẳng xác định được ở bài toán 1 ta sẽ xác định các hộ gia đình trong đoạn thẳng đó (xử lý dữ liệu).

* Với bài toán đầu tiên thì ta có thể xác định đơn giản đoạn thẳng cắt bởi các đường tròn tâm (x, y) bán kính f^2 và đường thẳng y = a bằng công thức: x_{p} - sqrt{f^{4}-(y-a)^{2}} leqslant x leqslant x_{p} + sqrt{f^{4}-(y-a)^{2}}
* Bài toán thứ 2, để có thể xác định được các hộ gia đình nằm trong đoạn thẳng đó, ta sắp xếp các hộ gia đình theo chiều tăng dần của hoành độ x và tìm kiếm (có thể dùng tìm kiếm nhị phân ) 2 mốc là 2 hoành độ của 2 gia đình đầu tiên và cuối cùng nằm trong khoảng đó. (x1 <= x <= x2).
động đất - siêu cúp olypic tin học 2012

Dưới đây là code:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct point {		// diem trong he toa do
    int x, y;
};

bool operator * ( const point &t, const point &u ){	// dinh nghia phep toan "*"
	return t.x > u.x;								//sap xep tang dan theo x
}

int my_compare (const void * a, const void * b){
	return ( *( point*)a * *(point*)b );			//chi duoc su dung phep toan "*" de sap xep
}

int main(){
    int n, p, k, ans = 0;
    cin >> n >> p >> k;

    point A[n], B[p];	//A[i] toa do cac ho gia dinh, B[i] toa do tam tran dong dat
    float f[p];			// cuong do tran dong dat thu i
    int c[n], A1[n];	// c[i] so tran dong dat ma ho gia dinh i phai chiu, 
						// A1[i] hoanh do cac ho gia dinh da sap xep

    for (int i = 0; i < n; i++) {				// nhap du lieu	
        cin >> A[i].x >> A[i].y;
        c[i] = 0;
    }
    
    for (int i = 0; i < p; i++) {				
        cin >> B[i].x >> B[i].y >> f[i];
    }

    qsort (A, n, sizeof(point), my_compare);	// sap xep cac ho gia dinh theo hoanh do
	for (int i = 0; i < n; i++)					// copy hoanh do cac ho gia dinh ra A1
		A1[i] = A[i].x;

    for (int i = 0; i <= 100; i++) {
        for (int j = 0 ; j < p; j++) {
			float temp = f[j]*f[j]*f[j]*f[j] - (B[j].y - i)*(B[j].y - i);
			if (temp >= 0){
				float x1 = B[j].x - sqrt(temp);
				float x2 = B[j].x + sqrt(temp);

				int temp1, temp2;
				
				temp1 = lower_bound(A1, A1 + n, x1) - A1;	// vi tri ho gia dinh dau tien trong doan x1, x2
				temp2 = upper_bound(A1, A1 + n, x2) - A1;
				temp2--;									// vi tri ho gia dinh cuoi cung trong doan x1, x2
				
				if (temp1 < n && temp2 < n) {				// tang so tran dong dat tai moi nha trong doan x1, x2
					for (int l = temp1; l <= temp2; l++)
						if (i == A[l].y) {
							c[l]++;
						}		
				}
			} 
        }
    }
    for (int i=0; i<n; i++)
		if (c[i] >= k) ans++ ;
	cout << ans << endl;
    return 0;
}

Trong đoạn code trên mình có sử dụng một số kỹ thuật và hàm:
– Sắp xếp mảng cấu trúc theo 1 thành phần của cấu trúc bằng QuickSort. Xem thêm tại Quick Sort – Các vấn đề liên quan
– Hàm lower_bound(A1, A1 + n, x1) trả về con trỏ trỏ đến phần tử đầu tiên >= x1 trong A1. Hàm upper_bound(A1, A1 + n, x2) trả về con trỏ trỏ đến phần tử đầu tiên > x2 trong A1. Vì vậy ta cần trừ đi A1 để được vị trí, và với temp2 cần giảm đi 1 đơn vị thì được x <= x2 là phần tử cuối cùng trong đoạn x1, x2 ta cần tìm.

Đề thi xem thêm tại: olp.vn