HDU Always Cook Mushroom (極角排序+樹狀數組)
來源：程序員人生 發布時間：2014-11-17 08:48:46 閱讀次數：2973次
Problem Description
Matt has a company, Always Cook Mushroom (ACM), which produces high-quality mushrooms.
ACM has a large field to grow their mushrooms. The field can be considered as a 1000 * 1000 grid where mushrooms are grown in grid points numbered from (1, 1) to (1000, 1000). Because of humidity and sunshine, the productions in different grid points are not
the same. Further, the production in the grid points (x, y) is (x + A)(y + B) where A, B are two constant.
Matt,the owner of ACM has some queries where he wants to know the sum of the productions in a given scope(include the mushroom growing on the boundary). In each query, the scope Matt asks is a right angled triangle whose apexes are (0, 0), (p, 0), (p, q) 1<=p,
q<=1000.
As the employee of ACM, can you answer Matt’s queries?
Input
The first line contains one integer T, indicating the number of test cases.
For each test case, the first line contains two integers:A, B(0<=A, B<=1000).
The second line contains one integer M(1<=M<=10^5), denoting the number of queries.
In the following M lines, the i-th line contains three integers a, b, x (1<=a, b<=10^6, 1<=x<=1000), denoting one apex of the given right angled triangle is (x, 0) and the slope of its base is (a, b). It is guaranteed that the gird points in the given right
angled triangle are all in valid area, numbered from (1, 1) to (1000, 1000).
Output
For each test case, output M + 1 lines.
The first line contains "Case #x:", where x is the case number (starting from 1)
In the following M lines, the i-th line contains one integer, denoting the answer of the i-th query.
Sample Input
2
0 0
3
3 5 8
2 4 7
1 2 3
1 2
3
3 5 8
2 4 7
1 2 3
Sample Output
Case #1:
1842
1708
86
Case #2:
2901
2688
200
Source
2014 ACM/ICPC Asia Regional Beijing Online
題意：給定1個1000x1000的點陣，m組詢問，每次詢問1個由(0,0)、(x,0)點1和從原點動身的方向向量(a,b)構成的直角3角形包圍的點的權值和。
思路: 預處理出這1e6個點的極角關系序，離線，將詢問也按(a,b)的極角排序。然后只需想象1根表針在逆時針的掃，把掃過的點的權值加到樹狀數組中，對每個詢問也僅僅是1個前綴和。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const int maxn = 1005;
const int inf = 1e5+5;
struct Point {
ll a, b;
double s;
} p[maxn*maxn];
struct Query {
ll a, b, x, id;
double s;
} q[maxn*maxn];
ll bit[maxn];
ll ans[inf], Index[inf];
int cnt;
void scan(ll &x) {
char c;
while ((c = getchar()) && (c < '0' || c > '9')) ;
x = c - '0';
while ((c = getchar()) && (c >= '0' && c <= '9'))
x = x * 10 + c - '0';
}
void out(ll x) {
if (x > 9)
out(x/10);
putchar(x%10+'0');
}
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int val) {
while (x <= 1000) {
bit[x] += val;
x += lowbit(x);
}
}
inline ll sum(int x) {
ll tmp = 0;
while (x > 0) {
tmp += bit[x];
x -= lowbit(x);
}
return tmp;
}
bool cmp1(Point x, Point y) {
return x.s < y.s;
}
bool cmp2(Query x, Query y) {
if (x.s == y.s)
return x.x < y.x;
return x.s < y.s;
}
void init() {
for (int i = 1; i <= 1000; i++)
for (int j = 1; j <= 1000; j++) {
p[cnt].a = i;
p[cnt].b = j;
p[cnt++].s = 1.0 * j / i;
}
sort(p, p+cnt, cmp1);
}
int main() {
cnt = 0;
ll A, B, m;
init();
int t, cas = 1;
scanf("%d", &t);
while (t--) {
memset(bit, 0, sizeof(bit));
scan(A), scan(B), scan(m);
for (int i = 0; i < m; i++) {
scan(q[i].a), scan(q[i].b), scan(q[i].x);
q[i].s = 1.0 * q[i].b / q[i].a;
q[i].id = i;
}
sort(q, q + m, cmp2);
for (int i = 0; i < m; i++) {
Index[q[i].id] = i;
}
cnt = 0;
printf("Case #%d:
", cas++);
for (int i = 0; i < m; i++) {
while (p[cnt].s <= q[i].s) {
add(p[cnt].a, (p[cnt].a+A) * (p[cnt].b + B));
cnt++;
}
ans[i] = sum(q[i].x);
}
for (int i = 0; i < m; i++) {
out(ans[Index[i]]);
printf("
");
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
