QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786811#5426. Drain the Water TankAweiWA 0ms3836kbC++142.2kb2024-11-26 23:39:022024-11-26 23:39:02

Judging History

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

  • [2024-11-26 23:39:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3836kb
  • [2024-11-26 23:39:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

struct point{
	double x, y;
};

double cross(point a, point b){
//    cout << a.x * b.y - b.x * a.y << endl;
    return a.x * b.y - b.x * a.y;
}

void solve(){
    int n;
    cin >> n;
    int lid = 1;
    vector<pair<int, int>> a(2 * n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
        if(a[i].second > a[lid].second) lid = i;
        else if(a[i].second == a[lid].second && a[i].first < a[lid].first) lid = i;
    }
    for(int i = 1; i <= n; i++){
        a[n + i] = a[i];
    }
    
    vector<point> b;
    int lx = a[lid].first;
    int ly = a[lid].second;
    for(int i = lid + 1; i <= n + lid; i++){
    	int x = a[i].first;
    	int y = a[i].second;
    	b.push_back({x - lx, y - ly});
    	lx = x; ly = y;
	}

    int ans = 0;
    bool ok = false;
    point down = {0, 0};
    for(int i = 0; i < b.size(); i++){
//    	cout << i << endl;
//		cout << down.x << " " << down.y << endl;
//		cout << b[i].x << " " << b[i].y << endl;
    	if(b[i].y > 0 && (down.x != 0 || down.y != 0)){
    		if(ok) ans++;
    		else if(cross(down, b[i]) >= 0){
    			ans++;
			}
			ok = false;
			down = {0, 0};
		}else if(b[i].y < 0){
			down = b[i];
		}else{
			ok = true;	
		}
//		cout << ans << endl;
//		cout << "-------" << endl;
	}
    
//    auto [lx, ly] = a[lid];
//    for(int i = lid + 1; i <= n + lid; i++){
//        auto [x, y] = a[i];
//        auto [xx, yy] = a[i + 1];
//        // cout << i << endl;
//        // cout << lx << " " << ly << endl;
//        // cout << x << " " << y << endl;
//        // cout << xx << " " << yy << endl;
//        if(y > ly){
//            lx = x;
//            ly = y;
//        }
//        if(yy > y && cross(x - lx, y - ly, xx - x, yy - y) >= 0){
//            lx = xx;
//            ly = yy;
//            ans++;
//        }
//        // cout << ans << endl;
//        // cout << "-------" << endl;
//    }
    cout << ans << "\n";
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

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

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

input:

3
0 0
100 0
0 100

output:

1

result:

ok 1 number(s): "1"

Test #10:

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

input:

3
200 0
100 100
0 0

output:

1

result:

ok 1 number(s): "1"

Test #11:

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

input:

3
50 50
100 50
100 100

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3
3 0
0 4
0 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

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

input:

3
10000 10000
-10000 10000
10000 9999

output:

1

result:

ok 1 number(s): "1"

Test #14:

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

input:

3
10000 10000
-10000 10000
10000 9900

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

input:

3
10000 10000
9999 10000
10000 -10000

output:

1

result:

ok 1 number(s): "1"

Test #16:

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

input:

3
0 0
200 0
100 173

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

3
0 0
200 0
100 1

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

3
-10000 -10000
10000 9999
9999 10000

output:

1

result:

ok 1 number(s): "1"

Test #19:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3524kb

input:

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

output:

2

result:

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