Posts 3: Earthquake
Limit the time for each test: 1 seconds.
On the banks of the river Lemon N households living. This residential area is frequently hit by many earthquakes with different intensity. Information about an earthquake Q includes a three integers (x, and, f), which:

– (x, and) is the location of the earthquake epicenter Q;
– f is the intensity of the earthquake at the epicenter measured Q (x,and).

A residential located at position (x’, Y') is said to be affected by an earthquake Q = (x, and, f) if:

Within the past month, earthquake monitoring center detected all P earthquakes occur in areas Chanh river. A supposedly households affected from the earthquake if it is influenced by at least K of P quake earthquake on. To assess the impact of the earthquake on the residential area on the bank of the river Lemon, local governments need to count the number of households affected from the earthquake on.

Request: For information about the earthquake and location of households, Please count the number of households affected from the earthquake that.
Data: In the text file includes N + P + EQ.INP 1 line:

– The first line contains 3 positive integer N, P, K (N ≤ 500000, P ≤ 5000);
– The next N lines contain information coordinates of N households. Ith row of N lines contains 2 xi integer , yi are the coordinates of the ith households (0 ≤ xi ≤ 10 6 , 0 ≤ yi ≤ 100).
– P line containing information about P earthquake. Ith row of P lines contains 3 xi integer , yi , fi is information on the ith earthquake.

Result: EQ.OUT given text file is an integer number of households affected from the earthquake.

==========

Actually, I also have to find the solution of the problem but have not seen any written page. His brothers and some have followed the following algorithm, of course not optimal, we're looking for to be able to share this post is a better way.

First we'll point out the easiest way that everyone can see it at every house, each house would quake lightning with P, if it affected the count increases (turn the night of earthquakes) to 1 or examine each quake, with each game the house at N. Finally we just count how many homes affected by k or more matches. Done bees @@
However, you can see our data with N <= 500.000 tripped <= 5.000 is too large to be carried out each test in 1 seconds. And we will learn how to better a little (unknown Is not the best way). =))

First we want to see it we will find points that are affected by the earthquake, The next job is just to count and compare the offer was subject to the k point or more matches. One important point we note that y<=100. So I will direct your attention to it.
We note that with each earthquake at its impact 1 center circle (x, and) f ^ 2 radius. Every straight line y = a (0 <= A <= 100) then for each earthquake if its impact will be 1 about (1 segment) and we need to determine which segment, followed by the identification of households within it and increase its count up. From here we take the problem of 2 subproblem:
1. Determining the straight lines cut by the circle created by the earthquake and the straight line y = a (data preparation).
2. For each segment identified in the problem 1 It will identify the families in which segments (data processing).

* With the first problem, we can identify simple straight lines cut by the center circle (x, and) f ^ 2 radius and straight line y = a formula:
* Problem No. 2, to be able to identify households in such straight lines, we arrange households in ascending the x coordinate and search (can use binary search ) 2 leaf 2 degree of diaphragmatic 2 Family first and last are within that range. (x1 <= x <= x2).

Here is the 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;
}

In the above code you have to use some of the techniques and functions:
– Sort array structured in 1 Components of the structure by Quicksort. See more at Quick Sort - Related Issues
– Hàm lower_bound(A1, A1 + n, x1) returns pointer to the first element >= X1 in A1. Hàm upper_bound(A1, A1 + n, x2) returns pointer to the first element > x2 in A1. So we need to subtract the A1 to the position, and the need to reduce travel temp2 1 Units shall be x <= X2 is the final element in paragraph x1, x2 we are looking.

To test more at: olp.vn