QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#437518 | #8669. 正方形计数 | SunsetGlow95 | 0 | 0ms | 3592kb | C++14 | 3.4kb | 2024-06-09 12:27:15 | 2024-06-09 12:27:15 |
answer
#include <bits/stdc++.h>
using namespace std;
struct Segment {
int l, r;
double k, b;
} upper[10], lower[10];
int upsz, lwsz;
// (x0, y0), (x0 + x, y0 + y), (x0 + x + y, y0 + y - x), (x0 + y, y0 - x)
int cal(int x, int y) {
int u1(0), u2(0), u3(0), u4(0), l1(0), l2(0), l3(0), l4(0), ans(0);
//cout << x << ',' << y << endl;
for (int i(upper[0].l);; ++i) {
while (u1 != upsz && upper[u1].r < i) ++u1;
while (u2 != upsz && upper[u2].r < i + x) ++u2;
while (u3 != upsz && upper[u3].r < i + x + y) ++u3;
while (u4 != upsz && upper[u4].r < i + y) ++u4;
while (l1 != lwsz && lower[l1].r < i) ++l1;
while (l2 != lwsz && lower[l2].r < i + x) ++l2;
while (l3 != lwsz && lower[l3].r < i + x + y) ++l3;
while (l4 != lwsz && lower[l4].r < i + y) ++l4;
if (u1 == upsz || u2 == upsz || u3 == upsz ||
u4 == upsz || l1 == lwsz || l2 == lwsz ||
l3 == lwsz || l4 == lwsz) break;
double up(min({upper[u1].k * i + upper[u1].b,
upper[u2].k * (i + x) + upper[u2].b - y,
upper[u3].k * (i + x + y) + upper[u3].b - y + x,
upper[u4].k * (i + y) + upper[u4].b + x}));
double lo(max({lower[l1].k * i + lower[l1].b,
lower[l2].k * (i + x) + lower[l2].b - y,
lower[l3].k * (i + x + y) + lower[l3].b - y + x,
lower[l4].k * (i + y) + lower[l4].b + x}));
up = floor(up), lo = ceil(lo);
// cout << i << ':' << up - lo + 1 << endl;
if (up >= lo) ans += up - lo + 1;
}
return ans;
}
int main() {
int N(0);
cin >> N;
vector<pair<int, int>> pts(N);
int mnx(1e9), mxx(0), mny(1e9), mxy(0);
for (auto &i : pts)
cin >> i.first >> i.second,
mnx = min(mnx, i.first),
mxx = max(mxx, i.first),
mny = min(mny, i.second),
mxy = max(mxy, i.second);
vector<Segment> ups, lws;
int pos(0);
while (pts[(pos + 1) % N].first <= pts[pos].first) pos = (pos + 1) % N;
while (pts[(pos + 1) % N].first > pts[pos].first) {
double k((pts[(pos + 1) % N].second - pts[pos].second) * 1.0 /
(pts[(pos + 1) % N].first - pts[pos].first));
double b(pts[pos].second - pts[pos].first * k);
ups.push_back(Segment{.l = pts[pos].first,
.r = pts[(pos + 1) % N].first, .k = k, .b = b});
pos = (pos + 1) % N;
}
while (pts[(pos + 1) % N].first >= pts[pos].first) pos = (pos + 1) % N;
while (pts[(pos + 1) % N].first < pts[pos].first) {
double k((pts[pos].second - pts[(pos + 1) % N].second) * 1.0 /
(pts[pos].first - pts[(pos + 1) % N].first));
double b(pts[pos].second - pts[pos].first * k);
lws.push_back(Segment{.l = pts[(pos + 1) % N].first,
.r = pts[pos].first, .k = k, .b = b});
pos = (pos + 1) % N;
}
reverse(lws.begin(), lws.end());
upsz = ups.size(), lwsz = lws.size();
copy(ups.begin(), ups.end(), upper), copy(lws.begin(), lws.end(), lower);
//for (auto i : ups) cout << i.l << ',' << i.r << ',' << i.k << ',' << i.b << endl;
//cout << "---" << endl;
//for (auto i : lws) cout << i.l << ',' << i.r << ',' << i.k << ',' << i.b << endl;
long long ans(0);
for (int x(0); x <= mxx - mnx; ++x) {
for (int y(1); y <= mxy - mny; y += 1) {
int t = cal(x, y);
// cout << x << ',' << y << ':' << t << endl;
ans += t;
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
4 131 603 131 1828 1919 1828 1919 603
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
3 131 603 131 1828 1919 603
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 15
Accepted
time: 0ms
memory: 3512kb
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
4047
result:
ok 1 number(s): "4047"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
8 0 4 1 15 2 15 15 14 15 4 14 0 1 0 0 2
output:
4200
result:
ok 1 number(s): "4200"
Test #13:
score: -15
Wrong Answer
time: 0ms
memory: 3508kb
input:
5 7 15 15 13 15 0 3 0 0 15
output:
1200
result:
wrong answer 1st numbers differ - expected: '3635', found: '1200'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%