QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857203#9882. Two Convex Setshos_lyricWA 2258ms118784kbC++145.0kb2025-01-15 12:12:172025-01-15 12:12:18

Judging History

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

  • [2025-01-15 12:12:18]
  • 评测
  • 测评结果:WA
  • 用时:2258ms
  • 内存:118784kb
  • [2025-01-15 12:12:17]
  • 提交

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] = sig(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: 4992kb

input:

4
0 0
3 0
0 3
1 1

output:

14

result:

ok "14"

Test #2:

score: 0
Accepted
time: 0ms
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: 0ms
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: 1ms
memory: 4992kb

input:

1
0 0

output:

2

result:

ok "2"

Test #5:

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

input:

2
1000000 0
0 1000000

output:

4

result:

ok "4"

Test #6:

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

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:

0

result:

ok "0"

Test #7:

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

input:

40
-865418 42040
-181476 58360
-864436 597211
-537311 -750515
653760 930646
-79954 431109
507863 569812
-756842 328289
-847028 -653883
-861260 953897
172940 -670358
-897079 -318722
-322040 580667
-110419 -862581
-673197 497171
160617 197820
-685798 -274098
-996233 -444341
-866456 -103514
884216 1302...

output:

0

result:

ok "0"

Test #8:

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

input:

40
-603027 -206745
522738 -843934
-230260 171562
409437 -780802
335077 938627
900036 446118
353133 613669
42034 -253742
897735 244447
162857 -205668
-291578 255993
-400956 -443041
363918 -151931
917921 -153303
-784264 -923508
707263 -65982
320014 -741462
69068 84317
-313477 -222217
398310 -623897
-3...

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 2253ms
memory: 118784kb

input:

40
304228 474832
339193 698218
532597 847991
301767 487867
301484 489588
312216 636492
301156 589241
864900 341382
815916 788658
902793 401404
383829 322243
311538 634321
934723 542442
934711 543872
849568 323602
317879 652850
297933 558903
545644 229664
426994 283936
932543 577716
803173 282502
612...

output:

1099511627776

result:

ok "1099511627776"

Test #10:

score: 0
Accepted
time: 2251ms
memory: 118784kb

input:

40
682213 413770
732917 632515
533711 341444
717776 670453
678714 725314
288718 555727
299151 498666
677853 726202
293244 521060
297629 503629
596562 779661
718283 465927
729188 643918
327210 694619
679785 724197
316576 458162
538430 793500
462138 788338
725100 654534
394541 375547
713627 457132
416...

output:

1099511627776

result:

ok "1099511627776"

Test #11:

score: 0
Accepted
time: 2244ms
memory: 118784kb

input:

40
690327 796610
899721 492039
415914 773849
868312 633436
551829 173087
893762 432825
426445 779673
625932 175784
710328 788345
880450 384750
454256 196451
318337 302277
540174 814957
255738 469043
894001 434064
698123 195603
526750 176060
829542 695452
343103 716386
326056 292299
771344 752130
450...

output:

1099511627776

result:

ok "1099511627776"

Test #12:

score: 0
Accepted
time: 2258ms
memory: 118784kb

input:

40
810134 763604
960023 517240
378773 299194
478204 770342
490699 777139
880031 704327
874167 270102
835337 234825
871394 713698
449497 229061
322449 426117
607498 811521
759209 191266
831662 748834
837502 744366
318150 527858
878136 274425
321341 431827
596871 810315
622934 812641
961137 489311
537...

output:

1099511627776

result:

ok "1099511627776"

Test #13:

score: 0
Accepted
time: 2235ms
memory: 118656kb

input:

40
396527 348618
490745 618330
623640 452117
516281 613752
569378 586849
400552 597147
481386 324337
556837 595804
536838 336715
510565 328020
381347 583103
622263 499529
336527 429250
342745 530846
462836 618172
351226 547269
341012 526731
621413 503618
624731 463870
585093 370850
353985 391507
463...

output:

1099511627776

result:

ok "1099511627776"

Test #14:

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

input:

40
348806 292250
881310 507145
648771 458522
350121 286404
528525 328171
523147 327950
877205 193023
646317 481228
650172 644274
592950 562001
491602 607700
633484 516916
561404 635604
464750 571606
472301 337351
345667 309392
918763 292245
410964 522730
414282 384403
493502 330811
560614 577972
398...

output:

96

result:

wrong answer 1st words differ - expected: '8', found: '96'