QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344910#3814. Saint John FestivalKhNURE_KIVI#AC ✓14ms4064kbC++203.8kb2024-03-05 18:34:072024-03-05 18:34:08

Judging History

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

  • [2024-03-05 18:34:08]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:4064kb
  • [2024-03-05 18:34:07]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

struct Point
{
    int x,y;
};

ostream& operator<<(ostream& os,const Point& a)
{
    return os<<"{"<<a.x<<","<<a.y<<"}";
}

const bool operator<(const Point& lhs,const Point& rhs)
{
    return mp(lhs.x,lhs.y)<mp(rhs.x,rhs.y);
}

Point operator-(const Point& lhs,const Point& rhs)
{
    return Point{lhs.x-rhs.x,lhs.y-rhs.y};
}

ll calc(const Point& a,const Point& b)
{
    return 1ll * a.x * b.y - 1ll * a.y * b.x;
}

bool cw(const Point& a,const Point& b)
{
    return 1ll * a.x * b.y - 1ll * a.y * b.x < 0;
}

bool ccw(const Point& a,const Point& b)
{
    return 0 < 1ll * a.x * b.y - 1ll * a.y * b.x;
}

bool cw(const Point& a,const Point& b,const Point& c)
{
    return cw(b-a, c-a);
}

bool ccw(const Point& a,const Point& b,const Point& c)
{
    return ccw(b-a, c-a);
}

vector<Point> convex_hull(vector<Point> v)
{
    sort(all(v));
    if (len(v)<=2){
        return v;
    }
    vector<Point> up,down;
    for (auto p:v){
        if (!ccw(v[0],p,v.back())){
            while (len(up)>=2 && !cw(up[len(up)-2],up.back(),p)){
                up.pop_back();
            }
            up.pb(p);
        }
    }
    for (auto p:v){
        if (!cw(v[0],p,v.back())){
            while (len(down)>=2 && !ccw(down[len(down)-2],down.back(),p)){
                down.pop_back();
            }
            down.pb(p);
        }
    }
    down.pop_back();
    reverse(all(down));
    down.pop_back();
    up.insert(up.end(), all(down));
    return up;
}

inline ll area (Point a, Point b, Point c) {
    return abs(calc(b - a, c - a));
}

inline bool inside(Point a, Point b, Point c, Point p) {
    return area(a, b, c) == area(a, b, p) + area(a, c, p) + area(b, c, p);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    vector<Point> v;
    for (int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        v.pb(Point{x,y});
    }
    auto H=convex_hull(v);

//    DEBUG{
//        cerr<<"up :: ";
//        for (auto i:up){
//            cerr<<i<<" ";
//        }
//        cerr<<"\n";
//        cerr<<"down :: ";
//        for (auto i:down){
//            cerr<<i<<" ";
//        }
//        cerr<<"\n";
//    };

    int ans=0;
    int q;
    cin>>q;
    LOG(q);
    while (q--){
        int x,y;
        cin>>x>>y;
        int l = 1, r = len(H) - 2;
        Point P{x, y};
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (!ccw(H[mid] - H[0], P - H[0])) {
                l = mid;
            }
            else {
                r = mid - 1;
            }
        }
        if (inside(H[0], H[r], H[r + 1], P)) {
            ++ans;
        }
    }
    cout<<ans<<"\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

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: 1ms
memory: 3564kb

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: 0ms
memory: 3548kb

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: 3820kb

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: 0ms
memory: 3544kb

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: 3824kb

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: 0ms
memory: 3492kb

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: 3536kb

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: 0ms
memory: 3592kb

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: 0ms
memory: 3544kb

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: 3600kb

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: 9ms
memory: 3740kb

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: 2ms
memory: 4064kb

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: 3808kb

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: 3700kb

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: 2ms
memory: 4048kb

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: 14ms
memory: 3744kb

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: 13ms
memory: 3680kb

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: 3764kb

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: 10ms
memory: 3696kb

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: 10ms
memory: 3764kb

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: 10ms
memory: 3788kb

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: 7ms
memory: 3728kb

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: 6ms
memory: 3704kb

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: 3796kb

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: 0ms
memory: 3616kb

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: 0ms
memory: 3828kb

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: 0ms
memory: 3576kb

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: 3548kb

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: 0ms
memory: 3636kb

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: 0ms
memory: 3840kb

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'