QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#437518#8669. 正方形计数SunsetGlow950 0ms3592kbC++143.4kb2024-06-09 12:27:152024-06-09 12:27:15

Judging History

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

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