### 第11届浙江大学校赛比赛点评beta » ZOJ3484

ZOJ3484.cpp

```#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 50;
const int MAXM = MAXN * MAXN;

struct Point {
int x, y;
Point() { }
Point(int x, int y) : x(x), y(y) { }
int abs2() const { return x * x + y * y; }
};

int operator*(const Point& lhs, const Point& rhs) {
return lhs.x * rhs.x + lhs.y * rhs.y;
}

int operator%(const Point& lhs, const Point& rhs) {
return lhs.x * rhs.y - lhs.y * rhs.x;
}

vector<Point> v[MAXM + 1], w;
// int c[MAXM + 1], ans[MAXN + 1];
int x[MAXM + 1][MAXM + 1];

double x;
scanf("%lf", &x);
int y = (int)(x * 100 + .5);
return y * y;
}

int main() {
int re;
int a, b, c, d, n;
Point p;

for (p.x = 0; p.x <= MAXN; ++p.x) {
for (p.y = -MAXN; p.y <= MAXN; ++p.y) {
if (p.abs2() <= MAXM) {
v[p.abs2()].push_back(p);
}
}
}
for (int i = 1; i <= MAXM; ++i) {
for (int j = 1; j <= i; ++j) {
set<int> s;
for (vector<Point>::const_iterator it = v[i].begin(); it != v[i].end(); ++it) {
for (vector<Point>::const_iterator jt = v[j].begin(); jt != v[j].end(); ++jt) {
if (*it * *jt >= 0 && *it % *jt > 0) {
s.insert(*it % *jt);
}
}
}
x[i][j] = s.size();
// c[i] += s.size();
}
}
/*
for (int i = 1; i <= MAXN; ++i) {
ans[i] = ans[i - 1];
for (int j = (i - 1) * (i - 1) + 1; j <= i * i; ++j) {
ans[i] += c[j];
}
}
*/
for (int i = 1; i <= MAXM; ++i) {
for (int j = 1; j <= MAXM; ++j) {
x[i][j] += x[i][j - 1];
}
for (int j = 1; j <= MAXM; ++j) {
x[i][j] += x[i - 1][j];
}
}

scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
//		scanf("%d", &n);
//		printf("%d\n", ans[n]);
a = (read() + 9999) / 10000 - 1;
c = (read() + 9999) / 10000 - 1;
n = 0;
n += x[b][d] + x[a]1 - x[a][d] - x[b]1;
n += x[d][b] + x1[a] - x[d][a] - x1[b];
a = max(a, c);
b = min(b, d);
if (a < b) {
n -= x[b][b] + x[a][a] - x[a][b] - x[b][a];
}
printf("%d\n", n);
}

return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//218 	2011-04-03 01:11:23 	Accepted 	H 	C++ 	1480 	24640 	watashi 	Source
```