QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#220209#5443. Security at MuseumshockyWA 1ms4140kbC++205.2kb2023-10-19 23:31:552023-10-19 23:31:56

Judging History

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

  • [2023-10-19 23:31:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4140kb
  • [2023-10-19 23:31:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef long long LL;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> PLL;
#define fi first
#define se second
#define pb push_back
#define rep(i,a,b) for(int i = a;i < b;i++)
#define all(a) begin(a), end(a)
#define sz(a) (int) a.size()
#define trav(nx, v) for(auto &nx : v)

const double EPS = 1e-9;
const double eps = 1e-9;

template<class T> inline bool eq(T x, T y) { return fabs(x - y) < EPS; }
template<class T> inline bool le(T x, T y) { return x < y + EPS; }
template<class T> inline bool lt(T x, T y) { return x + EPS < y; }
template<class T> inline T doubleMax(T x, T y) { return lt(x, y) ? y : x; }
template<class T> inline T doubleMin(T x, T y) { return lt(x, y) ? x : y; }
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
  typedef Point P;
  T x, y;
  explicit Point(T X = 0, T Y = 0) : x(X), y(Y) {}
  bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
  bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
  P operator+(P p) const { return P(x + p.x, y + p.y); }
  P operator-(P p) const { return P(x - p.x, y - p.y); }
  P operator*(T d) const { return P(x * d, y * d); }
  P operator/(T d) const { return P(x / d, y / d); }
  T dot(P p) const { return x * p.x + y * p.y; }
  T cross(P p) const { return x * p.y - y * p.x; }
  T cross(P a, P b) const { return (a - *this).cross(b - *this); }
  // return the orientation of (*this,a,b), 1 if ccw
  int ccw(P a, P b) const { return sgn((a - *this).cross(b - *this)); }
  T dist2() const { return x * x + y * y; }
  double dist() const { return sqrt((double)dist2()); }
  // angle to x-axis in interval [-pi, pi]
  double angle() const { return atan2(y, x); }
  P unit() const { return *this / dist(); } // makes dist()=1
  P perp() const { return P(-y, x); } // rotates +90 degrees
  P normal() const { return perp().unit(); }
  // returns point rotated 'a' radians ccw around the origin
  P rotate(double a) const {
    return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
  friend ostream& operator<<(ostream& os, P p) {
    return os << "(" << p.x << "," << p.y << ")";
  }
};

template <class P> bool segInter(P a, P b, P c, P d) {
  auto oa = c.cross(d, a), ob = c.cross(d, b);
  auto oc = a.cross(b, c), od = a.cross(b, d);
  if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
    return 1;
  return 0;
}

typedef long double LD;

typedef Point<LD> PD;
double segDist(PD& s, PD & e, PD &p) {
  if (s == e) return (p - s).dist();
  auto d = (e - s).dist2(), t = min(d, max(.0L, (p - s).dot(e - s )));
  return ((p - s) * d - (e - s) * t).dist() / d;
}

template<class P> bool onSegment(P s, P e, P p) {
  return segDist(s, e, p) < eps;
}

template<class P>
bool inPolygon(const vector <P> &p, P a, bool strict = true) {
  int cnt = 0, n = sz(p);
  rep(i, 0, n) {
    P q = p[(i + 1) % n];
    if (onSegment(p[i], q, a)) return !strict;
    cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
  }
  return cnt;
}

int isBad[205][205];

template<class P>
int solve(int u, int v, const vector <P> &isi) {
  if (u == v) return 0;
  if (u > v) return solve(v, u, isi);
  int &ret = isBad[u][v];
  if (~ret) return ret;
  int n = sz(isi);
  rep(k, 0, n) {
    if (k == u || k == v || (k + 1) % n == u || (k + 1) % n == v) continue;
    auto &a = isi[k], &b = isi[(k + 1) % n];
    auto &c = isi[u], &d = isi[v];
    if (onSegment(c, d, a)) return ret = solve(u, k, isi) || solve(k, v, isi);
    if (onSegment(c, d, b)) return ret = solve(u, (k + 1) % n, isi) || solve((k + 1) % n, v, isi);
    auto res = segInter(a, b, c, d);
    if (res) return ret = 1;
  }

  return ret = !inPolygon(isi, (isi[u] + isi[v]) / 2, false);
}

const ll MOD = 998244353;

typedef pair<int, int> PII;
typedef pair<PD, PII> Slope;
typedef array<int, 3> Container;
const int LIM = 200;
LL memo[2][LIM + 5][LIM + 5];
int main() {
  memset(isBad, -1, sizeof(isBad));
  cin.tie(0)->sync_with_stdio(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector <PD> isi(n);
  trav(cur, isi) cin >> cur.x >> cur.y;
  rep(i, 0, n) rep(j, 0, n) isBad[i][j] = isBad[j][i] = solve(i, j, isi);
  // rep(i,0,n) rep(j,0,n) cout << i << " " << j << " " << isBad[i][j] << endl;
  vector <int> perm(n);
  iota(all(perm), 0);
  sort(all(perm), [&](int a, int b) {
    return isi[a] < isi[b];
  });
  vector<Slope> slopes;
  rep(i, 0, n) rep(j, i + 1, n) {
    if (!isBad[perm[i]][perm[j]]) {
      slopes.pb({isi[perm[j]] - isi[perm[i]], {perm[i], perm[j]}});
    }
  }
  // Sort ccw
  stable_sort(all(slopes), [&](const Slope & a, const Slope & b) {
    auto res = a.fi.cross(b.fi);
    return le(0.0L, res);
    // Same slope case
  });
  rep(i, 0, n) memo[0][i][i] = memo[1][i][i] = 1;
  trav(slope, slopes) {
    int i = slope.se.fi, j = slope.se.se;
    rep(k, 0, n) {
      memo[0][i][k] = (memo[0][i][k] + memo[0][j][k]) % MOD;
      memo[1][j][k] = (memo[1][j][k] + memo[1][i][k]) % MOD;
    }
  }
  LL ans = 0;
  rep(i, 0, n) rep(j, 0, n) {
    ans += memo[0][i][j] * memo[1][j][i] % MOD;
  }
  cout << (ans - n + MOD) % MOD << endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 4120kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

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: 3952kb

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

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

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: 4016kb

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: 3928kb

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: 4024kb

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: 3904kb

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: 4128kb

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: 3980kb

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: 4028kb

input:

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

output:

41

result:

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