QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125738#3814. Saint John FestivalGoatGirl98AC ✓12ms3076kbC++143.9kb2023-07-17 15:03:042023-07-17 15:03:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 15:03:05]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:3076kb
  • [2023-07-17 15:03:04]
  • 提交

answer

#include <stdio.h>
#include <vector>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
typedef long long i64;
void wr(i64 x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + 48);
}
int rd()
{
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ '0');
        c = getchar();
    }
    return f > 0 ? k : -k;
}
struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    void input() { x = rd(), y = rd(); }
    point operator-(const point& o) const { return point(x - o.x, y - o.y); }
    // dot product of vector
    i64 operator*(const point& o) const { return 1ll * x * o.x + 1ll * y * o.y; }
    // cross product of vector 
    i64 operator^(const point& o) const { return 1ll * x * o.y - 1ll * y * o.x; }
    i64 dis2(const point& o) const { return 1ll * (x - o.x) * (x - o.x) + 1ll * (y - o.y) * (y - o.y); }
    bool operator<(const point& o) const { return (x ^ o.x) ? (x < o.x) : (y < o.y); }
    bool operator==(const point& o) const { return (x == o.x) && (y == o.y); }
};
// andrew O(nlogn)
// clockwise :      ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 1]])) <= 0
// anticlockwise :  ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0
vector<point> get_convex(vector<point>& points)
{
    int n = (int)points.size();
    sort(points.begin(), points.end());
    vector<int> stk;
    vector<bool> used(n);
    stk.push_back(0);
    // upper convex
    for (int i = 1; i < n; ++i)
    {
        while (stk.size() >= 2 && ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0)
            used[stk.back()] = false, stk.pop_back();
        used[i] = true, stk.push_back(i);
    }
    // stk.back() == n - 1
    // lower convex
    int upper_size = stk.size();
    for (int i = n - 2; i >= 0; --i)
    {
        if (used[i])
            continue;
        while (stk.size() > upper_size && ((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 2]])) <= 0)
            used[stk.back()] = false, stk.pop_back();
        used[i] = true, stk.push_back(i);
    }
    // stk.back() == stk[0]
    vector<point> ret;
    for (int i = 0; i < stk.size(); ++i)
        ret.push_back(points[stk[i]]);
    return ret;
}
bool in_convex(const vector<point>& hull, const point& p)
{
    int n = hull.size() - 1;
    if (n == 1)
        return p == hull[0];
    else if (n == 2)
        return (((p - hull[0]) ^ (hull[1] - hull[0])) == 0) && (((p - hull[0]) * (p - hull[1])) <= 0); 
    
    if (((p - hull[0]) ^ (hull[1] - hull[0])) > 0)
        return false;
    if (((p - hull[0]) ^ (hull[n - 1] - hull[0])) < 0)
        return false;
    int l = 1, r = n - 2;
    while (l <= r)
    {
        int mi = (l + r) >> 1;
        i64 a_1 = (hull[mi] - hull[0]) ^ (p - hull[0]), a_2 = (hull[mi + 1] - hull[0]) ^ (p - hull[0]);
        if (a_1 >= 0 && a_2 <= 0)
            return ((hull[mi + 1] - hull[mi]) ^ (p - hull[mi])) >= 0;
        else if (a_1 < 0)
            r = mi - 1;
        else
            l = mi + 1;
    }
    return false;
}
int main()
{
    int T = 1;
    for (int t = 1; t <= T; ++t)
    {
        // printf("Case %d:\n", t);
        int n = rd();
        vector<point> points(n);
        for (int i = 0; i < n; ++i)
            points[i].input();
        vector<point> hull = get_convex(points);
        int q = rd(), ans = 0;
        point p;
        while (q--)
            p.input(), ans += in_convex(hull, p);
        wr(ans), putchar('\n');
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 2884kb

input:

4
1 1
4 1
4 4
1 4
32
0 0
1 0
2 0
3 0
4 0
5 0
0 1
2 1
3 1
5 1
0 2
1 2
2 2
3 2
4 2
5 2
0 3
1 3
2 3
3 3
4 3
5 3
0 4
2 4
3 4
5 4
0 5
1 5
2 5
3 5
4 5
5 5

output:

12

result:

ok single line: '12'

Test #2:

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

input:

14
4 4
5 3
5 5
6 5
7 1
7 4
7 7
8 2
8 6
8 8
9 4
9 5
9 6
9 7
29
1 8
2 2
2 4
2 6
3 1
3 4
4 2
4 3
5 1
5 4
5 7
6 1
6 2
6 3
6 4
6 6
7 2
7 3
7 5
9 1
9 2
9 3
9 8
8 7
8 5
8 4
8 3
8 1
7 6

output:

13

result:

ok single line: '13'

Test #3:

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

input:

14
8 2
7 3
1 3
2 2
7 1
6 2
3 5
4 1
6 1
5 5
4 3
4 6
5 4
5 1
29
1 1
1 2
1 4
8 9
8 1
7 5
1 5
7 2
6 8
1 7
2 8
5 3
6 3
6 4
2 6
2 3
2 4
4 7
5 2
4 8
2 1
3 1
4 5
4 4
3 4
3 6
3 2
4 2
3 3

output:

13

result:

ok single line: '13'

Test #4:

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

input:

14
1 8
2 7
6 5
4 5
4 9
4 6
5 4
5 7
5 9
2 9
3 9
3 8
8 7
7 8
29
1 1
1 9
2 5
8 9
8 8
8 6
2 8
3 7
3 6
8 5
8 3
7 2
7 7
7 6
7 4
3 2
4 7
4 8
5 8
5 6
5 5
6 8
6 9
7 9
6 7
6 6
5 3
5 2
6 4

output:

13

result:

ok single line: '13'

Test #5:

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

input:

29
1 1
1 2
1 4
8 9
8 1
7 5
1 5
7 2
6 8
1 7
2 8
5 3
6 3
6 4
2 6
2 3
2 4
4 7
5 2
4 8
2 1
3 1
4 5
4 4
3 4
3 6
3 2
4 2
3 3
14
8 2
7 3
1 3
2 2
7 1
6 2
3 5
4 1
6 1
5 5
4 3
4 6
5 4
5 1

output:

14

result:

ok single line: '14'

Test #6:

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

input:

6
8 4
7 1
8 2
6 3
4 4
11 4
17
12 4
9 2
8 1
8 3
8 5
7 2
6 4
5 3
5 2
6 1
3 5
12 5
9 7
10 1
5 5
4 7
1 2

output:

4

result:

ok single line: '4'

Test #7:

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

input:

7
8 4
7 1
9 7
8 2
6 3
4 4
11 4
16
12 4
9 2
8 1
8 3
8 5
7 2
6 4
5 3
5 2
6 1
3 5
12 5
10 1
5 5
4 7
1 2

output:

5

result:

ok single line: '5'

Test #8:

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

input:

7
8 4
7 1
9 7
8 2
6 3
4 4
9 2
11
4 15
12 4
8 1
8 3
8 5
7 2
6 4
5 3
5 2
6 1
3 5

output:

5

result:

ok single line: '5'

Test #9:

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

input:

7
8 4
7 1
9 7
5 3
8 2
6 3
9 2
11
4 15
12 4
8 1
8 3
4 4
8 5
7 2
6 4
5 2
6 1
3 5

output:

4

result:

ok single line: '4'

Test #10:

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

input:

123
0 1
1 19
18 171
153 969
816 3876
3060 11628
8568 27132
18564 50388
31824 75582
43758 92378
48620 92378
43758 75582
31824 50388
18564 27132
8568 11628
3060 3876
816 969
153 171
18 19
1 1
3249 4142
5760 7676
8960 12236
25454 39216
26754 41496
27729 43206
32724 52288
33273 53447
34776 56620
36342 5...

output:

0

result:

ok single line: '0'

Test #11:

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

input:

20
0 1
1 19
18 171
153 969
816 3876
3060 11628
8568 27132
18564 50388
31824 75582
43758 92378
48620 92378
43758 75582
31824 50388
18564 27132
8568 11628
3060 3876
816 969
153 171
18 19
1 1
103
3249 4142
5760 7676
8960 12236
25454 39216
26754 41496
27729 43206
32724 52288
33273 53447
34776 56620
3634...

output:

103

result:

ok single line: '103'

Test #12:

score: 0
Accepted
time: 3ms
memory: 2936kb

input:

10000
313312 36161
6760 418062
329745 970120
756680 70914
140064 152948
169109 125153
791089 93470
452634 2249
45995 290528
107245 190577
822568 882033
68673 752896
135086 841815
2462 450445
30525 327974
277777 52098
523553 556
999985 496231
103196 804214
999632 519159
32 494346
944068 270211
985890...

output:

39321

result:

ok single line: '39321'

Test #13:

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

input:

9999
3549469 4957057
3566255 4982345
3589124 5016797
3609683 5047769
3618384 5060877
3704239 5190217
3706164 5193117
3744125 5250305
3788400 5317005
3814888 5356909
3839990 5394725
3866555 5434745
3919762 5514901
3989678 5620229
4024328 5672429
4044502 5702821
4103407 5791561
4110029 5801537
4128355...

output:

2785

result:

ok single line: '2785'

Test #14:

score: 0
Accepted
time: 2ms
memory: 2796kb

input:

9999
0 1
1 29
28 406
378 3654
3276 23751
20475 118755
98280 475020
376740 1560780
1184040 4292145
3108105 10015005
6906900 20030010
13123110 34597290
21474180 51895935
30421755 67863915
37442160 77558760
40116600 77558760
37442160 67863915
30421755 51895935
21474180 34597290
13123110 20030010
690690...

output:

2785

result:

ok single line: '2785'

Test #15:

score: 0
Accepted
time: 2ms
memory: 2840kb

input:

9999
3549469 4957056
3566255 4982345
3589124 5016793
3609683 5047761
3618390 5060870
3704240 5190220
3706164 5193124
3744125 525035
3788400 5317051
3814888 5356910
3839990 5394726
3866555 5434746
3919762 5514902
3989678 5620229
4024328 5672420
4044502 5702830
4103407 5791562
4110029 580153
4128355 5...

output:

2848

result:

ok single line: '2848'

Test #16:

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

input:

9999
0 1
1 29
28 406
378 3654
3276 23751
20475 118755
98280 475020
376740 1560780
1184040 4292145
3108105 10015005
6906900 20030010
13123110 34597290
21474180 51895935
30421755 67863915
37442160 77558760
40116600 77558760
37442160 67863915
30421755 51895935
21474180 34597290
13123110 20030010
690690...

output:

1553

result:

ok single line: '1553'

Test #17:

score: 0
Accepted
time: 12ms
memory: 2996kb

input:

10000
23643881 378592973
533158486 223946005
174971758 520074346
38244898 406529266
454636597 461791937
336498703 528098677
518880009 365053879
298059674 1639655
361899154 16796566
97198334 475160979
202005054 528521202
511752270 155057673
138672518 33447853
498626014 130341646
189343416 11916367
10...

output:

39178

result:

ok single line: '39178'

Test #18:

score: 0
Accepted
time: 5ms
memory: 3072kb

input:

10000
995653815 434217821
56510703 730905268
964656576 315353674
539542730 1566081
438892101 3748225
80893002 227329277
901720700 202308081
663486 474250336
93469941 208910134
9093396 594924738
537663402 1420550
566716347 995528938
849532269 857529288
900783492 201047509
793129623 905061752
96336930...

output:

39406

result:

ok single line: '39406'

Test #19:

score: 0
Accepted
time: 3ms
memory: 2852kb

input:

7514
0 1
1 28
27 378
351 3276
2925 20475
17550 98280
80730 376740
296010 1184040
888030 3108105
2220075 6906900
4686825 13123110
8436285 21474180
4686825 6906900
2220075 3108105
888030 1184040
296010 376740
80730 98280
17550 20475
2925 3276
351 378
27 28
1 1
10550 12243
54810 66360
65070 78995
21643...

output:

7461

result:

ok single line: '7461'

Test #20:

score: 0
Accepted
time: 9ms
memory: 3076kb

input:

10000
166957541 19920212
171502392 518758397
136610506 34598384
481877857 105647450
453295776 73796673
361741026 16737891
322309 255285010
92693973 471345596
390452858 507536580
519897724 362373316
60744921 98370071
4598010 317906620
245189121 1008454
233620571 534603669
328473301 530070796
20675490...

output:

3

result:

ok single line: '3'

Test #21:

score: 0
Accepted
time: 3ms
memory: 2844kb

input:

10000
166957541 19920212
171502392 518758397
136610506 34598384
481877857 105647450
453295776 73796673
361741026 16737891
322309 255285010
92693973 471345596
390452858 507536580
519897724 362373316
60744921 98370071
4598010 317906620
245189121 1008454
233620571 534603669
328473301 530070796
20675490...

output:

2

result:

ok single line: '2'

Test #22:

score: 0
Accepted
time: 6ms
memory: 2964kb

input:

10000
166957541 19920212
171502392 518758397
136610506 34598384
481877857 105647450
453295776 73796673
361741026 16737891
322309 255285010
92693973 471345596
390452858 507536580
519897724 362373316
60744921 98370071
4598010 317906620
245189121 1008454
233620571 534603669
328473301 530070796
20675490...

output:

2

result:

ok single line: '2'

Test #23:

score: 0
Accepted
time: 6ms
memory: 2844kb

input:

10000
313312 36161
6760 418062
329745 970120
756680 70914
140064 152948
169109 125153
791089 93470
452634 2249
45995 290528
107245 190577
822568 882033
68673 752896
135086 841815
2462 450445
30525 327974
277777 52098
523553 556
999985 496231
103196 804214
999632 519159
32 494346
944068 270211
985890...

output:

39194

result:

ok single line: '39194'

Test #24:

score: 0
Accepted
time: 3ms
memory: 2960kb

input:

10000
166957541 19920212
171502392 518758397
136610506 34598384
481877857 105647450
453295776 73796673
361741026 16737891
322309 255285010
92693973 471345596
390452858 507536580
519897724 362373316
60744921 98370071
4598010 317906620
245189121 1008454
233620571 534603669
328473301 530070796
20675490...

output:

1

result:

ok single line: '1'

Test #25:

score: 0
Accepted
time: 2ms
memory: 2732kb

input:

5
100 50
50 150
130 190
200 50
55 145
21874
185 101
171 86
104 115
67 137
53 166
57 50
80 155
133 175
119 90
66 66
160 114
199 51
146 189
95 98
118 129
87 191
189 106
122 63
108 126
71 138
94 57
131 49
121 110
84 102
107 79
70 81
93 144
164 109
97 70
106 156
177 127
163 60
186 135
59 127
82 52
125 9...

output:

12126

result:

ok single line: '12126'

Test #26:

score: 0
Accepted
time: 2ms
memory: 2760kb

input:

6
50 150
55 145
160 180
100 50
130 190
200 50
21873
185 101
171 86
104 115
67 137
53 166
57 50
80 155
133 175
119 90
66 66
160 114
199 51
146 189
95 98
118 129
87 191
189 106
122 63
108 126
71 138
94 57
131 49
121 110
84 102
107 79
70 81
93 144
164 109
97 70
106 156
177 127
163 60
186 135
59 127
82 ...

output:

13850

result:

ok single line: '13850'

Test #27:

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

input:

5
1 2
15 2
5 10
10 1
2 1
5
5 6
11 2
10 6
16 2
12 5

output:

3

result:

ok single line: '3'

Test #28:

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

input:

4
0 0
0 5
5 5
5 0
45
1 3
6 6
3 0
3 2
2 1
6 2
1 6
5 1
2 5
0 3
4 0
1 2
3 3
1 5
4 4
6 3
5 6
3 6
2 2
3 5
4 1
1 1
6 4
5 4
2 6
4 5
0 4
6 0
1 4
2 3
2 4
4 2
1 0
6 5
5 3
0 1
4 6
3 4
6 1
3 1
0 6
2 0
4 3
5 2
0 2

output:

32

result:

ok single line: '32'

Test #29:

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

input:

6
10 5
5 15
13 19
20 5
16 18
6 14
456
7 3
16 9
19 4
17 20
20 7
18 19
21 6
8 5
9 0
10 7
0 17
14 1
12 17
15 4
13 20
3 2
4 5
16 0
19 13
17 13
20 14
18 10
21 15
8 12
9 9
10 14
8 18
11 15
9 19
14 8
12 8
15 13
13 13
2 18
0 14
3 11
1 15
4 12
2 12
5 1
3 17
16 7
19 18
17 6
7 15
18 5
21 8
10 9
11 4
9 20
14 19...

output:

143

result:

ok single line: '143'

Test #30:

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

input:

14
2 1
3 2
5 4
6 5
1 2
2 3
4 4
5 6
1 3
3 5
1 4
1 5
2 7
3 8
29
4 7
4 3
1 1
1 6
1 7
1 8
2 2
2 4
2 5
2 6
2 8
3 3
3 4
3 6
3 7
4 5
4 6
5 5
5 2
5 8
4 8
6 6
6 7
7 5
7 8
8 3
8 5
8 7
9 1

output:

13

result:

ok single line: '13'

Test #31:

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

input:

8
3 4
2 8
5 4
1 8
4 7
3 10
11 2
7 3
6
5 12
3 7
3 3
4 5
0 4
2 6

output:

3

result:

ok single line: '3'