QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#437506 | #8669. 正方形计数 | SunsetGlow95 | 0 | 0ms | 3536kb | C++14 | 3.4kb | 2024-06-09 12:00:04 | 2024-06-09 12:00:04 |
answer
#include <bits/stdc++.h>
using namespace std;
struct Segment {
int l, r;
double k, b;
};
// (x0, y0), (x0 + x, y0 + y), (x0 + x + y, y0 + y - x), (x0 + y, y0 - x)
int cal(const vector<Segment>& upper, const vector<Segment>& lower,
int x, int y) {
int u1(0), u2(0), u3(0), u4(0), l1(0), l2(0), l3(0), l4(0), ans(0);
for (int i(upper[0].l); i <= upper.back().r; ++i) {
while (u1 != upper.size() && upper[u1].r < i) ++u1;
while (u2 != upper.size() && upper[u2].r < i + x) ++u2;
while (u3 != upper.size() && upper[u3].r < i + x + y) ++u3;
while (u4 != upper.size() && upper[u4].r < i + y) ++u4;
while (l1 != lower.size() && lower[l1].r < i) ++l1;
while (l2 != lower.size() && lower[l2].r < i + x) ++l2;
while (l3 != lower.size() && lower[l3].r < i + x + y) ++l3;
while (l4 != lower.size() && lower[l4].r < i + y) ++l4;
if (u1 == upper.size() || u2 == upper.size() || u3 == upper.size() ||
u4 == upper.size() || l1 == lower.size() || l2 == lower.size() ||
l3 == lower.size() || l4 == lower.size()) 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[u1].k * i + lower[u1].b,
lower[u2].k * (i + x) + lower[u2].b - y,
lower[u3].k * (i + x + y) + lower[u3].b - y + x,
lower[u4].k * (i + y) + lower[u4].b + x}));
up = floor(up), lo = ceil(lo);
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> upper, lower;
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);
upper.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);
lower.push_back(Segment{.l = pts[(pos + 1) % N].first,
.r = pts[pos].first, .k = k, .b = b});
pos = (pos + 1) % N;
}
reverse(lower.begin(), lower.end());
//for (auto i : upper) cout << i.l << ',' << i.r << ',' << i.k << ',' << i.b << endl;
//for (auto i : lower) 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(upper, lower, 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: 0
Wrong Answer
time: 0ms
memory: 3536kb
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
4401
result:
wrong answer 1st numbers differ - expected: '4047', found: '4401'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%