QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417027#523. 部落战争Max_s_xaM100 ✓74ms12076kbC++174.2kb2024-05-22 13:15:052024-05-22 13:15:06

Judging History

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

  • [2024-05-22 13:15:06]
  • 评测
  • 测评结果:100
  • 用时:74ms
  • 内存:12076kb
  • [2024-05-22 13:15:05]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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