QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560247 | #8669. 正方形计数 | ORzyzRO | 0 | 1875ms | 3676kb | C++14 | 7.6kb | 2024-09-12 14:34:14 | 2024-09-12 14:34:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int, int>
#define pb push_back
#define mid (l + r) / 2
#define ls num << 1
#define rs num << 1 | 1
inline int read() {
int x = 0, m = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') m = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * m;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
write(-x);
return;
}
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
#define double long double
const double eps = 1e-10, Pi = acos(-1), inf = 1e6;
const int N = 20;
struct dot {
double x, y;
dot(double x = 0, double y = 0) : x(x), y(y) {}
} a[N];
struct Vec {
double x, y;
Vec(double x = 0, double y = 0) : x(x), y(y) {}
};
struct line {
dot x, y;
pr k, b;
line(dot x = dot(), dot y = dot(), pr k = {0, 0}, pr b = {0, 0}) : x(x), y(y), k(k), b(b) {}
double angle() {
return atan2(y.y - x.y, y.x - x.x);
}
} b[N], c[N], h[N], A[4];
line rev(line x) {
return line(x.y, x.x, x.k, x.b);
}
Vec operator - (dot x, dot y) {
return Vec(y.x - x.x, y.y - x.y);
}
dot operator + (dot x, Vec y) {
return dot(x.x + y.x, x.y + y.y);
}
line operator + (line x, Vec y) {
pr now = x.b;
now.first += y.y * now.second;
now.first -= x.k.first * y.x;
return line(x.x + y, x.y + y, x.k, now);
}
int dcmp(double x) {
if (fabs(x) < eps) return 0;
return (x > 0) ? 1 : -1;
}
double operator * (Vec x, Vec y) {
return x.x * y.y - x.y * y.x;
}
double operator == (dot x, dot y) {
return dcmp(x.x - y.x) == 0 && dcmp(x.y - y.y) == 0;
}
bool check(Vec x, Vec y) {
return dcmp(x * y) < 0;
}
bool check(line x, dot y) {
return check(x.y - x.x, y - x.x);
}
dot cross(line x, line y) {
Vec x1 = y.y - x.x, x2 = x.y - x.x, x3 = y.x - x.x;
double S1 = x1 * x2, S2 = x3 * x2;
return dot((S1 * y.x.x - S2 * y.y.x) / (S1 - S2), (S1 * y.x.y - S2 * y.y.y) / (S1 - S2));
}
bool operator < (line x, line y) {
double xt = x.angle();
double yt = y.angle();
if (dcmp(xt - yt) != 0) return xt < yt;
if (x.x == y.x) return check(x, y.y);
return check(x, y.x);
}
int f(int n, int a, int b, int c) {
if (n < 0) return 0;
if (!n) return (b / c);
if (!a) return (n + 1) * (b / c);
if (a >= c || b >= c) return (n + 1) * (b / c) + n * (n + 1) / 2 * (a / c) + f(n, a % c, b % c, c);
int M = (a * n + b) / c;
return n * M - f(M - 1, c, c - b - 1, a);
}
int calc(int l, int r, int a, int b, int c) {
b += c;
// cout << " Query " << l << ' ' << r << ' ' << a << ' ' << b << ' ' << c << ' ';
if (l > r) return 0;
if (a == 0) {
if (b < 0) return 0;
return (r - l + 1) * (b / c);
}
if (a < 0) {
b = a * r + b;
r = r - l;
l = 0;
a = -a;
}
// cout << "[" << l << ' ' << r << ' ' << a << ' ' << b << ' ' << c << "] ";
if (b < 0) {
l = max(l, (-b + a - 1) / a);
if (l > r) return 0;
b = a * l - b;
r = r - l;
l = 0;
}
return f(r, a, b, c) - f(l - 1, a, b, c);
}
int calc(int n) {
double minn = 2000, maxn = 0;
for (int i = 1; i <= n; i++) {
minn = min(minn, a[i].x);
maxn = max(maxn, a[i].x);
}
if (minn == maxn) {
if (dcmp(ceil(minn) - minn) != 0) return 0;
minn = 2000;
maxn = 0;
for (int i = 1; i <= n; i++) {
minn = min(minn, a[i].y);
maxn = max(maxn, a[i].y);
}
return floor(maxn) - ceil(minn) + 1;
}
int ans = 0;
dot A(minn, -2000);
for (int i = 1; i <= n; i++) {
int x = i % n + 1;
if (dcmp(a[i].x - a[x].x) == 0) continue;
double l = min(a[i].x, a[x].x), r = max(a[i].x, a[x].x);
int L = ceil(l), R = floor(r);
if (dcmp(l - minn) != 0 && dcmp(L - l) == 0) L++;
int a = h[i].k.first, b = h[i].b.first, c = h[i].k.second;
assert(h[i].k.second == h[i].b.second && h[i].k.second != 0);
if (check(h[i], A)) {
b--;
// cout << " Dec";
int res = calc(L, R, a, b, c);
ans -= res;
// cout << res << '\n';
}
else {
// cout << " Add";
int res = calc(L, R, a, b, c);
ans += res;
// cout << res << '\n';
}
}
return ans;
}
signed main() {
int n = read(), maxx = 0, minx = 2000, maxy = 0, miny = 2000;
for (int i = 1; i <= n; i++) {
a[i].x = read();
a[i].y = read();
maxx = max(maxx, (int)a[i].x);
minx = min(minx, (int)a[i].x);
maxy = max(maxy, (int)a[i].y);
miny = min(miny, (int)a[i].y);
}
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
int x = i % n + 1;
int X = a[x].x - a[i].x, Y = a[x].y - a[i].y;
int k = __gcd(X, Y);
X /= k;
Y /= k;
if (X < 0) X = -X, Y = -Y;
int Z = a[i].y * X - a[i].x * Y;
b[i] = line(a[i], a[x], {Y, X}, {Z, X});
}
sort(b + 1, b + n + 1);
int limx = maxx - minx, limy = maxy - miny;
int V = max(limx, limy), ans = 0;
for (int x = 0; x <= limx; x++) {
for (int y = x; x + y <= V && y <= limy; y++) {
if (!y) continue;
Vec x1(-x, y);
Vec x2(-y, -x);
Vec x3(-x - y, y - x);
for (int i = 1; i <= n; i++) {
A[0] = b[i];
A[1] = b[i] + x1;
A[2] = b[i] + x2;
A[3] = b[i] + x3;
sort(A, A + 4);
c[i] = A[0];
}
int l = 1, r = 0, P = 1;
for (int i = 1; i <= n; i++) {
while (l < r && check(c[i], a[r])) r--;
while (l < r && check(c[i], a[l + 1])) l++;
h[++r] = c[i];
// for (int j = l; j <= r; j++) {
// printf("(%.3Lf, %.3Lf) (%.3Lf, %.3Lf)\n", h[j].x.x, h[j].x.y, h[j].y.x, h[j].y.y);
// }
// putchar('\n');
if (l < r) {
if (dcmp(fabs(h[r - 1].angle() - h[r].angle()) - Pi) == 0 && check(h[r], h[r - 1].x)) {
P = 0;
break;
}
a[r] = cross(h[r - 1], h[r]);
}
}
if (P) {
while (l < r && check(h[l], a[r])) r--;
a[l] = cross(h[l], h[r]);
P = 1;
for (int i = 1; i <= n; i++) {
if (check(c[i], a[l])) {
P = 0;
break;
}
}
if (P) {
for (int i = 1; i <= r - l + 1; i++) a[i] = a[i + l - 1], h[i] = h[i + l - 1];
if (l + 1 < r) {
// for (int i = 1; i <= r - l + 1; i++) {
// printf("(%.3Lf, %.3Lf) (%.3Lf %.3Lf) (%.3Lf %.3Lf)\n", a[i].x, a[i].y, h[i].x.x, h[i].x.y, h[i].y.x, h[i].y.y);
// }
int res = calc(r - l + 1);
// cout << ' ' << x << ' ' << y << ' ' << res << '\n';
ans += res;
}
}
}
}
}
write(ans);
putchar('\n');
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1875ms
memory: 3652kb
input:
4 131 603 131 1828 1919 1828 1919 603
output:
181368388464
result:
wrong answer 1st numbers differ - expected: '361182910200', found: '181368388464'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 1725ms
memory: 3676kb
input:
3 131 603 131 1828 1919 603
output:
30566051316
result:
wrong answer 1st numbers differ - expected: '63739309181', found: '30566051316'
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 1ms
memory: 3520kb
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
1143
result:
wrong answer 1st numbers differ - expected: '4047', found: '1143'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%