QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417027 | #523. 部落战争 | Max_s_xaM | 100 ✓ | 74ms | 12076kb | C++17 | 4.2kb | 2024-05-22 13:15:05 | 2024-05-22 13:15:06 |
Judging History
answer
#include <iostream>
#include <algorithm>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 2e5 + 10;
int n, m, q, tot;
struct Point
{
int x, y;
Point operator + (const Point u) const {return Point{x + u.x, y + u.y};}
Point operator - (const Point u) const {return Point{x - u.x, y - u.y};}
ll operator * (const Point u) const {return (ll)x * u.y - (ll)y * u.x;}
ll length() {return (ll)x * x + (ll)y * y;}
}a[MAXN], b[MAXN], c[MAXN], d[MAXN];
inline bool cmp1(Point u, Point v) {return u.y == v.y ? u.x < v.x : u.y < v.y;}
inline bool cmp2(Point u, Point v) {ll t = u * v; return (!t ? u.length() < v.length() : t > 0);}
int st[MAXN], top;
inline void Convex(Point *p, int &n)
{
sort(p + 1, p + n + 1, cmp1);
Point z = p[1];
for (int i = 1; i <= n; i++) p[i] = p[i] - z;
sort(p + 2, p + n + 1, cmp2);
st[top = 1] = 1;
for (int i = 2; i <= n; i++)
{
while (top > 1 && (p[i] - p[st[top]]) * (p[st[top]] - p[st[top - 1]]) >= 0) top--;
st[++top] = i;
}
for (int i = 1; i <= top; i++) p[i] = p[st[i]] + z;
n = top, p[n + 1] = p[1];
}
inline void Minkowski()
{
for (int i = 1; i <= n; i++) c[i] = a[i + 1] - a[i];
for (int i = 1; i <= m; i++) d[i] = b[i + 1] - b[i];
a[tot = 1] = a[1] + b[1];
for (int i = 1, j = 1; i <= n || j <= m;)
if (j > m || (i <= n && c[i] * d[j] >= 0)) a[tot] = a[tot++] + c[i++];
else a[tot] = a[tot++] + d[j++];
}
inline bool Check(Point op)
{
int pos = lower_bound(a + 1, a + tot + 1, op, cmp2) - a;
if (pos == tot + 1 || (a[pos] - op) * (op - a[pos - 1]) < 0) return 0;
return 1;
}
int main()
{
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(m), Read(q);
for (int i = 1; i <= n; i++) Read(a[i].x), Read(a[i].y);
for (int i = 1; i <= m; i++) Read(b[i].x), Read(b[i].y), b[i].x = -b[i].x, b[i].y = -b[i].y;
Convex(a, n), Convex(b, m);
// for (int i = 1; i <= n; i++) cout << a[i].x << ' ' << a[i].y << '\n';
// cout << '\n';
// for (int i = 1; i <= m; i++) cout << b[i].x << ' ' << b[i].y << '\n';
Minkowski(), Convex(a, tot);
Point z = a[1], op;
for (int i = 1; i <= tot; i++) a[i] = a[i] - z;
while (q--)
{
Read(op.x), Read(op.y);
cout << Check(op - z) << '\n';
}
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 2ms
memory: 11820kb
input:
5 5 500 6407435 3293303 7667584 -28726709 12981947 3232993 -4728920 -20310419 11417244 -21375059 -9897535 1003568 11250465 -455741 -212338 27421583 -8617310 23838234 1170809 22010017 9475604 -55467994 -4050339 3741774 -837777 3712301 21965125 2292518 15461481 -52915993 6607803 -55284619 4978498 3464...
output:
1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 ...
result:
ok 500 lines
Test #2:
score: 10
Accepted
time: 1ms
memory: 9832kb
input:
5 5 500 -27523822 3903432 -8164905 12245974 -12788492 -18439238 -9257256 12571383 -7088899 -13518632 8395941 908038 3503624 10427724 -14313118 13946163 -8810192 15122696 -23606580 1742581 -2846782 -33320015 10422149 -23265478 -28254784 -10728385 -25177201 8093012 -7071570 -16767903 -24720747 8309611...
output:
0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 ...
result:
ok 500 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 9776kb
input:
50 50 500 4254966 4514473 -10243311 29338943 -11714256 28967870 -3638225 -329846 -11636788 -126679 -5182905 -625577 6032976 21796923 -13140961 28452003 1041973 27162958 -2756343 -84802 -7820141 29623403 -1439665 28473013 -2457947 28853419 -7990305 29616231 -7601697 29629812 -14884269 1278440 -998615...
output:
1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 ...
result:
ok 500 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 11872kb
input:
50 50 500 9401701 -3609043 2012208 -1102882 -1811540 -26010495 -5041437 -3110073 10286335 -4329717 12578870 -20602424 10667571 -4684127 12022858 -6227670 6703376 -2076756 -3916528 -2467881 -8883942 -6948248 4710266 -26206538 8123463 -24867007 5052685 -26121576 -4028108 -2524942 -1941055 -1669813 319...
output:
1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 ...
result:
ok 500 lines
Test #5:
score: 10
Accepted
time: 7ms
memory: 9880kb
input:
10000 10000 500 1666056 -27430003 -4367330 9570472 18716225 -12240967 -1787485 -27373792 -15436704 1726451 5020083 -26867542 -2574044 -27271537 -11443050 6074066 -4820607 -26789265 15100955 2873536 -9623440 7349040 976214 10130141 -9144842 7634171 6079703 9216512 15077673 -20242861 16905511 69303 13...
output:
0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 ...
result:
ok 500 lines
Test #6:
score: 10
Accepted
time: 3ms
memory: 9944kb
input:
10000 10000 500 9282217 -4781364 1501964 25031109 -3834648 -5391055 8360673 -5218666 -7317209 -3446949 -10874263 199999 -3638519 23977553 -10806642 104184 9180387 23342430 8585209 23627902 -742433 24790641 2593801 -6522640 -13108369 4871264 -3278720 24111737 -1204794 24700179 2670075 25028975 145219...
output:
0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 ...
result:
ok 500 lines
Test #7:
score: 10
Accepted
time: 7ms
memory: 9944kb
input:
10000 10000 500 18739956 22581499 226899 20847190 4459986 -8474225 19625260 22085584 17107612 -8505721 1592846 21819795 4911498 -8647734 754040 -6425195 11298530 -9694797 8002434 -9467273 15632721 -9011669 19047199 -7595729 26034505 15249508 1304680 21631076 16199900 -8834823 20427260 -6752268 -5838...
output:
0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 ...
result:
ok 500 lines
Test #8:
score: 10
Accepted
time: 74ms
memory: 12076kb
input:
100000 100000 100000 24235601 -13951926 -10355885 -24094242 -5635989 -27027698 12252374 12885344 6137155 -28841530 15967851 10799403 9725989 13814468 -7061607 12038424 -9834599 -24505790 11646839 -27414386 -2187954 -28266157 -18126630 -3597220 3069276 14729493 -199316 14425458 11896146 -27311875 -12...
output:
0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 ...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 69ms
memory: 11024kb
input:
100000 100000 100000 8354421 -26671439 8956353 6194768 18000019 5113843 -731040 989961 20842988 3589967 1941343 -23926046 17724523 5225919 26327648 -18097349 26513711 -2848520 19914037 -24750782 19992615 -24705163 -3889910 -4001319 26006870 -1907798 11797680 6399489 3081377 -24663720 14262223 -26766...
output:
0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 ...
result:
ok 100000 lines
Test #10:
score: 10
Accepted
time: 72ms
memory: 10396kb
input:
100000 100000 100000 -17714771 -18844934 13960381 -21362034 -13107507 -24716099 -5216508 -28653304 -6830004 7079906 -7371497 6895381 15737377 -2830941 -16200790 -21359312 -17628244 -19016144 8224158 -26586063 -732489 7976996 13458776 -22030283 -5650557 -28549478 16498589 -4770663 4862335 -28120485 8...
output:
1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 ...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed