投稿 3: 地震
各テストの時間を制限: 1 秒.
生きている川レモンN世帯のほとり. この住宅地は頻繁に異なる強度を有するいくつかの地震に襲われます. Qは3の整数を含んで地震に関する情報 (X, と, F), これ:

– (X, と) 地震の震源のQの場所があります;
– fは震源測定Qの地震の強度であります (X,と).

位置にある住宅 (バツ', Y ') 地震のQによって影響されると言われています= (X, と, F) もし:

先月, 地震監視センターは、すべてのPの地震が川エリアレモンに発生が検出されました. 住宅の世帯は、それがP地震地震の少なくともKの影響を受けている場合には、地震から影響を受けると言われています. 川レモンの土手に住宅地への震災の影響を評価するために、, 地方自治体は上の震災からの影響を受けた世帯の数をカウントする必要があります.

リクエスト: 世帯の地震や場所に関する情報については, その地震から影響を受けた世帯の数をカウントしてください.
データ: テキストファイルからではN + P + EQ.INP 1行が含まれています:

– 最初の行が含まれています 3 整数N, P, K (N≤ 500000, P≤ 5000);
– 次のNラインはN情報世帯の座標を含みます. N行のi番目の行が含まれてい 2 XI整数 , 李氏はi番目の世帯の座標であります (0 ≤≤XI 10 6 , 0 ≤李≤ 100).
– Pの地震に関する情報を含むPライン. i番目のラインはラインPが含まれています 3 XI整数 , YI , Fiはi番目の地震の情報であります.

結果: 与えられたテキストファイルEQ.OUT整数は震災からの影響を受けた世帯の数であります.

==========

実は、私はまた、問題の解決策を見つけるために持っていますが、任意の書かれたページを見ていません. 彼の兄弟といくつかは次のアルゴリズムに従いました, もちろん、最適ではありません, 我々はこのポストを共有できるように探しているのより良い方法です.

まず、誰もがすべての家でそれを見ることができる最も簡単な方法を通過します, 各家はPと地震雷だろう, それが増加した数に影響を与えた場合 (地震の夜を回します) アップ 1 または各地震で, 各Nで家を一致させると. 最後に、私たちは上向きにマッチKの影響を受けてどのように多くの家庭数えます. 蜂を完了@@
しかし、あなたはNで私たちのデータを見ることができます <= 500.000 そしてP <= 5.000 各テストを実行するには大きすぎます 1 秒. そして、私たちは少しのより良い方法を学習します (未知のは最善の方法ではありません). =))

まず、私たちは震災の影響の点を見つけることを確認したいです, 次の仕事はただ古いKと一致することを拒否された任意の点をカウントし、比較することです. 我々はyのことに注意してもう一つの重要なポイント<= 100. だから我々はそれに注意を描画します.
私たちは、各レベルの地震とその影響であることに注意してください 1 センターサークル (X, と) 半径はF ^ 2であります. すべて直線y = A (0 <= A <= 100) その後、各地震のためにその影響がなる場合 1 スペース (1 セグメント) そして、私たちはどのセグメントを決定する必要があります, 次にそれに世帯を特定し、そのカウントを増加させることです. ここから我々は問題を取ります 2 サブ問題:
1. 地震と直線y = Aによって作成された円で切断セグメントを識別する (データ準備).
2. 数学で識別された各セグメントについて 1 私は、このような直線で世帯を識別します (情報処理).

* 最初の問題で、我々はセンターサークルでカットし、単純な直線を識別することができます (X, と) F ^ 2つの半径と直線Yは、式=:
* 第二の問題 2, で直線家族を識別するために, 我々は、x座標の昇順と検索で家庭を手配します (バイナリ検索を使用することができます ) 2 金型は、 2 のx座標 2 範囲内の最初と最後の家族のこと. (X1 <= X <= x2の).

ここでは、コードです:

#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;
}

上記のコードでは、私は技術および機能の数を使用します:
– ソート配列は、構造化 1 クイックソートによる構造のコンポーネント. で詳細を参照してください。 クイックソート - 関連の問題
– ハムLOWER_BOUND(A1, A1 + N, X1) 最初の要素へのポインタを返します >A1で= X1. ハムUPPER_BOUND(A1, A1 + N, X2) 最初の要素へのポインタを返します > X2 A1. だから我々は、位置にA1を減算する必要があります, 旅行TEMP2を低減し、必要 1 単位は、xしなければなりません <= X2は、セグメントX1の最後の要素であります, 私たちが見ているX2.

試験より: olp.vn