QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857200#9882. Two Convex Setshos_lyricWA 27ms6656kbC++144.9kb2025-01-15 12:09:472025-01-15 12:09:48

Judging History

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

  • [2025-01-15 12:09:48]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:6656kb
  • [2025-01-15 12:09:47]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

inline int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
inline Int sq(Int r) { return r * r; }
struct Pt {
  Int x, y;
  Pt() : x(0), y(0) {}
  Pt(Int x_, Int y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Pt &operator/=(const Int &k) { x /= k; y /= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
  bool operator!=(const Pt &a) const { return !(x == a.x && y == a.y); }
  bool operator<(const Pt &a) const { return ((x != a.x) ? (x < a.x) : (y < a.y)); }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
inline Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }


int N;
Pt P[41];

int T[41][41][41];
Int pre[41][41][41];
Int suf[41][41][41];

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int u = 0; u < N; ++u) {
      scanf("%lld%lld", &P[u].x, &P[u].y);
    }
    
    sort(P, P + N);
    sort(P + 1, P + N, [&](const Pt &a, const Pt &b) -> bool {
      return (tri(P[0], a, b) > 0);
    });
cerr<<"P = ";pv(P,P+N);
    
    for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) for (int w = 0; w < N; ++w) {
      T[u][v][w] = tri(P[u], P[v], P[w]);
    }
    
    memset(pre, 0, sizeof(pre));
    memset(suf, 0, sizeof(suf));
    pre[0][0][0] = 1;
    map<vector<int>, Int> crt;
    for (int u = 1; u < N; ++u) {
      // advance to u
      map<vector<int>, Int> nxt;
      for (int v = 0; v <= u - 1; ++v) for (int w = 0; w <= v; ++w) if (pre[u - 1][v][w]) {
        if (T[u][v][w] <= 0) {
          pre[u][u][v] += pre[u - 1][v][w];
        }
        nxt[vector<int>{u - 1, v, u, u, u, u}] += pre[u - 1][v][w];
        suf[u][v][w] += pre[u - 1][v][w];
      }
      for (const auto &kv : crt) {
// if(N<=4)cerr<<kv<<endl;
        const auto &us = kv.first;
        if (T[u][us[0]][us[1]] <= 0) {
          auto vs = us; vs[1] = vs[0]; vs[0] = u;
          nxt[vs] += kv.second;
        }
        if (T[u][us[2]][us[3]] <= 0) {
          auto vs = us; vs[3] = vs[2]; vs[2] = u;
          nxt[vs] += kv.second;
        }
        if (T[u][us[4]][us[5]] >= 0) {
          auto vs = us; vs[5] = vs[4]; vs[4] = u;
          nxt[vs] += kv.second;
        }
        if (T[u][us[2]][us[3]] <= 0 && T[u][us[4]][us[5]] >= 0) {
          suf[u][us[0]][us[1]] += kv.second;
        }
      }
      for (int v = 0; v <= u - 1; ++v) for (int w = 0; w <= v; ++w) if (suf[u - 1][v][w]) {
        if (T[u][v][w] <= 0) {
          suf[u][u][v] += suf[u - 1][v][w];
        }
      }
      crt.swap(nxt);
    }
    
    Int ans = 0;
    for (int v = 0; v <= N - 1; ++v) for (int w = 0; w <= v; ++w) {
      ans += pre[N - 1][v][w];
      ans += suf[N - 1][v][w];
    }
    ans *= 2;
    printf("%lld\n", ans);
  }
  return 0;
}

详细

Test #1:

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

input:

4
0 0
3 0
0 3
1 1

output:

14

result:

ok "14"

Test #2:

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

input:

8
1 0
2 0
3 1
3 2
2 3
1 3
0 2
0 1

output:

256

result:

ok "256"

Test #3:

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

input:

10
0 0
1 1
7 1
1 7
3 2
2 3
4 2
2 4
5 4
4 5

output:

0

result:

ok "0"

Test #4:

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

input:

1
0 0

output:

2

result:

ok "2"

Test #5:

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

input:

2
1000000 0
0 1000000

output:

4

result:

ok "4"

Test #6:

score: -100
Wrong Answer
time: 27ms
memory: 6656kb

input:

40
675677 -903121
254211 732097
792262 -321884
701349 560077
430182 -715346
404091 -587385
-368483 765887
-62363 -93377
964720 739688
-63560 -743279
-445506 491429
758128 486841
571801 -759073
-838475 443367
238435 -29645
651624 -991716
-747006 397530
-616854 -868231
656953 925190
-317709 453131
-16...

output:

31566386

result:

wrong answer 1st words differ - expected: '0', found: '31566386'