QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423654#5443. Security at Museumsu2x1WA 1ms3588kbC++204.9kb2024-05-28 14:41:182024-05-28 14:41:20

Judging History

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

  • [2024-05-28 14:41:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3588kb
  • [2024-05-28 14:41:18]
  • 提交

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; }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }

struct Line { Pt s, t; };

bool ptOnSeg(Pt x, Line v) {
  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) {
  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) {
  return (ptOnSeg(a.s, b) || ptOnSeg(a.t, b)
   || ptOnSeg(b.s, a) || ptOnSeg(b.t, a));
}

bool segInter_strict(Line a, Line b) {
  return (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);
}

bool segInPoly(Line s, const 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, inferior = side(a, b, c) > 0;
      for (auto x : {s.s, s.t}) {
        if (inferior) {
          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;
}

bool vis[201];
int dp[201];

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; segs.reserve(n*n);
  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; };

  auto cmp = [&](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::sort(all(segs), cmp);
  std::vector<int> id(n); std::iota(all(id), 0);
  std::sort(all(id), [&](int a, int b) { return polys[a] < polys[b]; });
  lnt ret = 0;

  const unsigned int mo = 998244353;
  std::multiset<std::pair<int, int>, decltype(cmp)> ssegs(cmp);
  for (auto x : segs) {
    ssegs.emplace(x);
  }
  for (int _ = 0; _ < n; ++_) {
    int u = id[_];
    memset(dp, 0, sizeof(dp));
    dp[u] = 1;
    vis[u] = true;
    for (auto it = ssegs.begin(); it != ssegs.end(); ) {
      auto [a, b] = *it;
      dp[b] = (dp[b] + dp[a]) % mo;
      if (vis[a] || vis[b]) { it = ssegs.erase(it); }
      else { ++it; }
    }
    ret = (ret + dp[u] - 1 + mo) % mo;
  }

  auto ksm = [&](lnt x, unsigned 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(); ) {
    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]};
      if (sign(a.t - a.s) - sign(b.t - b.s)) { break; }
      if (sgn(det(a.t - a.s, b.t - b.s))) { break; }
      if (!segInter(a, b)) { break; }
      a.t = b.t;
      ++j;
    }
    for (int k = 1; ; ++k) {
      if (k * (k + 1) / 2 == j - i) {
        if (k == 1) { break; }
        for (int w = 1; w < k; ++w) {
          for (lnt z = w, c = 1, f = 1; z < k; ) {
            ret = (ret - ksm(2, c) * f % mo) % mo;
            f = (f * 2 + 1) % mo;
            ++z, ++c;
          }
        }
        break;
      }
    }
    i = j;
  }

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

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3588kb

input:

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

output:

33

result:

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