QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419409#5443. Security at Museumsu2x1WA 1ms3820kbC++205.5kb2024-05-23 21:41:032024-05-23 21:41:04

Judging History

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

  • [2024-05-23 21:41:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2024-05-23 21:41:03]
  • 提交

answer

#include "bits/stdc++.h"

#define all(x)   x.begin(), x.end()
#define NL       std::cout << '\n'

using lnt = long long;

const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 61;

using db = double; const db eps = 1e-12;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }

struct Pt { db x, y; };
std::istream& operator>>(std::istream& is, Pt &p) {
  int x, y; std::cin >> x >> y;
  p.x = x; p.y = y; return is;
}
std::ostream& operator<<(std::ostream& os, Pt p) {
  return os << "(" << p.x << "," << p.y << ")";
}

Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator!=(Pt a, Pt b) { return sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
db dis2(Pt a, Pt b) { return dot(a-b, a-b); }
db dis(Pt a, Pt b) { return std::sqrt(dis2(a, b)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
Pt rot90(Pt a) { return {-a.y, a.x}; }
Pt rot(Pt a, db t) {
  return { a.x * std::cos(t) - a.y * std::sin(t)
         , a.x * std::sin(t) + a.y * std::cos(t) };
}
Pt unit(Pt a) {
  db d = dis(a, {0, 0});
  return sgn(d) ? a/d : Pt{0, 0};
}

struct Line { Pt s, t; };

bool ptOnSeg(Pt x, Line v) {
  if (v.s == v.t) { return sgn(dis2(v.s, x)) == 0; }
  return sgn(det(v.s - x, v.t - x)) == 0
      && sgn(dot(v.s - x, v.t - x)) <= 0;
}

bool ptOnSegStrict(Pt x, Line v) {
  if (v.s == v.t) { return sgn(dis2(v.s, x)) == 0; }
  return sgn(det(v.s - x, v.t - x)) == 0
      && sgn(dot(v.s - x, v.t - x)) < 0;
}

bool segInter(Line a, Line b) {
  if (sgn(det(b.s-a.s, a.t-a.s)) * sgn(det(b.t-a.s, a.t-a.s)) == -1
   && sgn(det(a.s-b.s, b.t-b.s)) * sgn(det(a.t-b.s, b.t-b.s)) == -1) {
    return true;
  }
  if (ptOnSeg(a.s, b) || ptOnSeg(a.t, b)
   || ptOnSeg(b.s, a) || ptOnSeg(b.t, a)) {
    return true;
  }
  return false;
}

bool segInter_strict(Line a, Line b) {
  if (sgn(det(b.s-a.s, a.t-a.s)) * sgn(det(b.t-a.s, a.t-a.s)) == -1
   && sgn(det(a.s-b.s, b.t-b.s)) * sgn(det(a.t-b.s, b.t-b.s)) == -1) {
    return true;
  }
  return false;
}

bool segInPoly(Line s, std::vector<Pt> &v) {
  const int n = v.size();
  for (int i = 0; i < n; ++i) {
    const Pt a = v[i], b = v[(i+1) % n], c = v[(i+2) % n];
    if (segInter_strict(s, {a, b})) { return false; }
    if (ptOnSeg(b, s)) {
      bool ok = true, acute = side(a, b, c) > 0;
      for (auto x : {s.s, s.t}) {
        if (acute) {
          ok &= side(a, b, x) >= 0 && side(b, c, x) >= 0;
        } else {
          ok &= side(a, b, x) >= 0 || side(b, c, x) >= 0;
        }
      }
      if (!ok) { return false; }
    }
  }
  return true;
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int n; std::cin >> n;
  std::vector<Pt> polys(n);
  for (int i = 0; i < n; ++i) { std::cin >> polys[i]; }
  std::vector<std::pair<int, int>> segs;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (!segInPoly({polys[i], polys[j]}, polys)) { continue; }
      segs.push_back({i, j});
      segs.push_back({j, i});
    }
  }
  auto sign = [](Pt u) -> int { return (u.y > eps || (sgn(u.y) == 0 && u.x > eps)) ? 1 : -1; };

  std::sort(all(segs), [&](auto i, auto j) {
      Line a = {polys[i.first], polys[i.second]}, b = {polys[j.first], polys[j.second]};
      int dir = sign(a.t-a.s) - sign(b.t-b.s);
      if (dir) { return dir > 0; }
      dir = sgn(det(a.t-a.s, b.t-b.s));
      if (dir) { return dir > 0; }
      dir = sgn(det(a.t-a.s, b.t-a.s));
      if (dir) { return dir < 0; }
      dir = sgn(dot(a.t-a.s, b.t-a.t));
      return dir > 0;
      });

  std::vector<int> id(n); std::iota(all(id), 0);
  std::sort(all(id), [&](int a, int b) { return sign(polys[a] - polys[b]) == -1; });
  lnt ret = 0;
  const int mo = 998244353;
  std::basic_string<bool> vis(n, 0);
  for (int _ = 0; _ < n; ++_) {
    int u = id[_];
    std::vector<int> dp(n);
    dp[u] = 1;
    for (auto [a, b] : segs) {
      if (vis[a] || vis[b]) { continue; }
      dp[b] = (dp[b] + dp[a]) % mo;
    }
    ret = (ret + dp[u] - 1 + mo) % mo;
    vis[u] = true;
  }

  auto ksm = [&](lnt x, int e) {
    lnt ret = 1;
    while (e) {
      if (e & 1) { ret = ret * x % mo; }
      x = x * x % mo; e >>= 1;
    }
    return ret;
  };

  for (int i = 0; i < segs.size(); ++i) {
    Line a = {polys[segs[i].first], polys[segs[i].second]};
    if (sign(a.t - a.s) == -1) { break; }
    int j = i + 1;
    while (j < segs.size()) {
      Line b = {polys[segs[j].first], polys[segs[j].second]};
      int dir = sign(a.t - a.s) - sign(b.t - b.s);
      if (dir) { break; }
      dir = sgn(det(a.t - a.s, b.t - b.s));
      if (dir) { break; }
      if (segInter(a, b)) {
        ++j;
      } else { break; }
    }
    for (int k = 1; ; ++k) {
      if (k * (k + 1) / 2 == j - i) {
        if (k > 1) {
          for (int w = 1; w < k; ++w) {
            for (int z = w, c = 1, f = 1; z < k; ++z, ++c, f = f * 2 + 1) {
              ret -= ksm(2, c) * f;
            }
          }
        }
        break;
      }
      assert(k <= n);
    }
    i = j - 1;
  }

  ret = (ret % mo + mo) % mo;
  std::cout << ret; NL;

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3808kb

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

44

result:

ok 1 number(s): "44"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

93

result:

ok 1 number(s): "93"

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

7
0 0
50 50
80 20
110 50
70 90
40 60
0 100

output:

56

result:

wrong answer 1st numbers differ - expected: '44', found: '56'