QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740222#5426. Drain the Water TankZawos#WA 0ms3784kbC++141.3kb2024-11-13 04:21:422024-11-13 04:21:43

Judging History

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

  • [2024-11-13 04:21:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3784kb
  • [2024-11-13 04:21:42]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
struct pt{
    ll x,y;
    pt():x(0),y(0){}
    pt(ll x,ll y): x(x),y(y){}
    pt operator+(pt p){return pt(x+p.x,y+p.y);}
    pt operator-(pt p){return pt(x-p.x,y-p.y);}
    ll cross(pt p){return (*this).x*p.y-(*this).y*p.x;}
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    vector<pt> v(n);
    FOR(i,0,n) cin >> v[i].x >> v[i].y;
    int index = 0;
    for(int i = 0; i< n; i++){
        if(v[(i+1)%n].y > v[i].y){
            index = i;
            break;
        }
    }
    int p1 = (index+1)%n;
    int ans = 0;
    int need = 0;
    for(int i = 0; i < n; i++){
        if(v[(p1+1)%n].y < v[p1].y){
            need = 1;
        }
        if(need && v[(p1+1)%n].y > v[p1].y && (v[(p1+1)%n]-v[p1]).cross(v[(p1+n-1)%n]-v[(p1)%n]) >= 0){
            ans++;
            need = 0;
        }
        p1++;
        p1%=n;
    }
    cout << ans <<'\n';

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
0 0
1 1
2 1
3 0
3 2
0 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

7
1 0
3 4
0 3
1 2
2 3
1 1
0 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

8
0 0
1 0
3 -1
3 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

5
0 0
170 0
140 30
60 30
0 70

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

input:

5
0 0
170 0
140 30
60 30
0 100

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

5
0 0
1 2
1 5
0 2
0 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

3
0 0
100 0
0 100

output:

1

result:

ok 1 number(s): "1"

Test #10:

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

input:

3
200 0
100 100
0 0

output:

1

result:

ok 1 number(s): "1"

Test #11:

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

input:

3
50 50
100 50
100 100

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3
3 0
0 4
0 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

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

input:

3
10000 10000
-10000 10000
10000 9999

output:

1

result:

ok 1 number(s): "1"

Test #14:

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

input:

3
10000 10000
-10000 10000
10000 9900

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

input:

3
10000 10000
9999 10000
10000 -10000

output:

1

result:

ok 1 number(s): "1"

Test #16:

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

input:

3
0 0
200 0
100 173

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

3
0 0
200 0
100 1

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

3
-10000 -10000
10000 9999
9999 10000

output:

1

result:

ok 1 number(s): "1"

Test #19:

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

input:

4
10 10
20 10
20 20
10 20

output:

1

result:

ok 1 number(s): "1"

Test #20:

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

input:

4
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

1

result:

ok 1 number(s): "1"

Test #21:

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

input:

4
100 0
200 100
100 200
0 100

output:

1

result:

ok 1 number(s): "1"

Test #22:

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

input:

4
0 1
100 0
101 100
1 101

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

4
0 0
100 0
100 50
0 50

output:

1

result:

ok 1 number(s): "1"

Test #24:

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

input:

4
0 0
50 0
50 100
0 100

output:

1

result:

ok 1 number(s): "1"

Test #25:

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

input:

4
0 10
10 0
100 90
90 100

output:

1

result:

ok 1 number(s): "1"

Test #26:

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

input:

8
0 100
100 0
250 0
350 100
350 250
250 350
100 350
0 250

output:

1

result:

ok 1 number(s): "1"

Test #27:

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

input:

6
0 50
10 0
70 0
80 10
70 50
50 80

output:

1

result:

ok 1 number(s): "1"

Test #28:

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

input:

4
0 100
0 0
100 0
20 20

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

4
0 100
55 55
100 0
100 100

output:

1

result:

ok 1 number(s): "1"

Test #30:

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

input:

8
0 0
100 0
100 20
40 20
40 40
100 40
100 60
0 60

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

12
0 0
90 0
90 30
40 30
40 40
90 40
90 50
0 50
0 20
50 20
50 10
0 10

output:

1

result:

ok 1 number(s): "1"

Test #32:

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

input:

12
0 0
100 0
100 100
10 100
10 110
200 110
200 60
101 60
101 40
210 40
210 120
0 120

output:

2

result:

ok 1 number(s): "2"

Test #33:

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

input:

10
1000 0
1100 0
1200 100
1220 200
1200 110
1100 10
1000 10
900 110
880 200
900 100

output:

1

result:

ok 1 number(s): "1"

Test #34:

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

input:

16
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #35:

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

input:

8
0 1
100 0
5 5
200 5
105 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #36:

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

input:

8
0 1
50 0
5 5
200 5
150 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #37:

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

input:

9
99 100
100 100
99 99
301 99
300 100
301 100
201 274
200 273
199 274

output:

1

result:

ok 1 number(s): "1"

Test #38:

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

input:

15
0 0
10 0
20 0
30 0
40 0
50 0
40 10
30 20
20 30
10 40
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

11
0 0
100 0
90 5
80 10
70 15
60 20
50 25
40 20
30 15
20 10
10 5

output:

1

result:

ok 1 number(s): "1"

Test #40:

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

input:

8
0 0
20 30
0 60
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #41:

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

input:

18
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 30
120 60
120 90
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #42:

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

input:

15
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #43:

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

input:

11
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #44:

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

input:

9
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #45:

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

input:

29
0 0
100 0
100 50
0 50
0 20
80 20
80 30
10 30
10 40
20 40
30 40
40 40
50 40
60 40
70 40
80 40
90 40
90 30
90 20
90 10
80 10
70 10
60 10
50 10
40 10
30 10
20 10
10 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #46:

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

input:

24
0 0
100 0
100 100
200 100
200 0
300 0
300 100
300 200
200 200
200 300
300 300
300 400
300 500
200 500
200 400
100 400
100 500
0 500
0 400
0 300
100 300
100 200
0 200
0 100

output:

2

result:

ok 1 number(s): "2"

Test #47:

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

input:

4
50 50
100 50
100 101
50 100

output:

1

result:

ok 1 number(s): "1"

Test #48:

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

input:

10
100 300
150 50
100 0
200 50
250 150
250 50
400 0
300 50
350 50
400 300

output:

2

result:

ok 1 number(s): "2"

Test #49:

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

input:

10
300 400
50 350
50 300
0 400
50 250
150 250
50 200
0 100
50 150
300 100

output:

2

result:

ok 1 number(s): "2"

Test #50:

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

input:

5
0 0
100 100
60 40
200 200
40 60

output:

2

result:

ok 1 number(s): "2"

Test #51:

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

input:

5
0 0
100 100
60 40
120 120
40 60

output:

2

result:

ok 1 number(s): "2"

Test #52:

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

input:

5
0 0
100 100
51 49
200 200
49 51

output:

2

result:

ok 1 number(s): "2"

Test #53:

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

input:

5
100 10
300 0
200 10
400 10
300 20

output:

1

result:

ok 1 number(s): "1"

Test #54:

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

input:

5
20 300
10 400
10 200
0 300
10 100

output:

1

result:

ok 1 number(s): "1"

Test #55:

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

input:

10
110 171
57 121
56 102
7 17
101 24
65 34
70 43
157 6
134 20
93 54

output:

2

result:

ok 1 number(s): "2"

Test #56:

score: -100
Wrong Answer
time: 0ms
memory: 3748kb

input:

28
90 55
160 20
323 47
418 138
371 386
367 225
321 305
306 115
284 436
281 216
233 86
231 227
219 312
216 405
213 45
184 92
182 345
168 462
155 275
136 107
106 211
100 159
94 308
85 232
62 413
43 160
0 338
16 95

output:

3

result:

wrong answer 1st numbers differ - expected: '1', found: '3'