QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857203 | #9882. Two Convex Sets | hos_lyric | WA | 2258ms | 118784kb | C++14 | 5.0kb | 2025-01-15 12:12:17 | 2025-01-15 12:12:18 |
Judging History
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'