QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#437506#8669. 正方形计数SunsetGlow950 0ms3536kbC++143.4kb2024-06-09 12:00:042024-06-09 12:00:04

Judging History

你现在查看的是最新测评结果

  • [2024-06-09 12:00:04]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3536kb
  • [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%