QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857200 | #9882. Two Convex Sets | hos_lyric | WA | 27ms | 6656kb | C++14 | 4.9kb | 2025-01-15 12:09:47 | 2025-01-15 12:09:48 |
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] = 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'