[巴解组织] 地震的问题 – OLP信息 2012 超级块
帖子 3: 地震
限制每次测试的时间: 1 秒.
在河柠檬ñ户居住的银行. 这是一个住宅区往往遭受地震强度不同. 关于地震的信息Q包括三个整数 (X, 和, ˚F), 哪:
– (X, 和) 是Q地震的震中;
– f是在震中测得的地震Q的大小 (X,和).
一个家庭位于该位置 (X', 和') 据推测受地震影响Q = (X, 和, ˚F) 如果:
过去一个月内, 地震监测中心检测到在清河地区发生的所有P地震. 如果一个家庭至少受到上述P次地震中的K次地震的影响，则据说该家庭受到地震的严重影响。. 评估地震对昌河两岸居民区的影响, 地方当局需要计算受地震严重影响的家庭数量.
要求: 提供有关地震和家庭所在地的信息, 计算受地震严重影响的家庭数量.
数据: 从文本文件EQ.INP输入，包括N + P + 1行:
– 第一行包含 3 正整数N, P, ķ (N≤ 500000, P≤ 5000);
– 接下来的N行包含N个住户的坐标. N行中的第i行包含 2 整数xi , yi是第i户的坐标 (0 ≤ xi ≤ 10 6 , 0 ≤ yi ≤ 100).
– 接下来的P行包含有关P地震的信息. P行的第i行包含 3 整数xi , yi , fi是地震信息.
结果: 给EQ.OUT文本文件一个整数，该整数是受地震严重影响的家庭数量.
==========
实际上，我也已经搜索了问题的解决方案，但是没有找到任何写的页面. 我的一些兄弟遵循以下算法, 当然还不是最佳的, 我们希望您能更好地完成本课.
首先，我们将回顾任何人看到的最简单的方法是考虑每所房子, 每一座房子我们都会像地震一样闪电, 如果受到影响，请增加计数 (转夜地震号) 向上 1 或考虑每次地震, 每场比赛，考虑N座房屋. 最后，我们只需要计算有多少间房屋受到k场或更多场比赛的影响. 就是这样，蜜蜂@@
但是您可以使用N查看我们的数据 <= 500.000 和P <= 5.000 太大，无法执行每个测试 1 秒. 我们将学习更好的方法 (不确定这是否是最好的方法). =))
首先，我们看到需要解决的问题，我们将寻找受地震影响的点, 接下来的事情是计算并比较哪些得分超过k个游戏. 我们注意到的重要一点是<=100. 所以我们将注意力转向它.
我们注意到，每次地震的影响程度为 1 中心圆 (X, 和) 半径是f ^ 2. 每行y = a (0 <= A <= 100) 那么每一次地震 1 大约 (1 直段) 我们需要确定那条线, 下一步是确定其中的住户并增加其数量. 从这里我们将问题带回来 2 儿童问题:
1. 确定穿过地震产生的圆和线y = a的线段 (数据准备).
2. 对于问题中确定的每条直线 1 我们将识别该行中的家庭 (数据处理).
* 对于第一个问题，我们可以简单地定义与中心圆相交的线段 (X, 和) 半径f ^ 2和线y = a等于公式:
* 数学问题 2, 能够识别该行中的家庭, 我们沿着x坐标的升序排列住户并进行搜索 (可以使用二进制搜索 ) 2 地标是 2 隔膜 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 + ñ, X1) 返回指针的第一个元素 >= A1中的x1. Hàmupper_bound(A1, A1 + ñ, X2) 返回指针的第一个元素 > A1中的x2. 所以我们需要减去A1来获得位置, 并随着temp2需要降低 1 单位x <= x2是段落x1中的最后一个元素, x2我们需要找到.
查看更多考试: 奥尔普
最新评论