QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786857#5426. Drain the Water TankAweiWA 0ms3836kbC++142.3kb2024-11-27 00:09:352024-11-27 00:09:36

Judging History

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

  • [2024-11-27 00:09:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3836kb
  • [2024-11-27 00:09:35]
  • 提交

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 ok1 = false, ok2 = true;
    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;
//		cout << ok2 << endl;
    	if(b[i].y > 0){
			if(ok2 && (down.x != 0 || down.y != 0)){
    			if(ok1) ans++;
    			else if(cross(down, b[i]) >= 0){
    				ans++;
				}
			}
			ok1 = false;
			down = {0, 0};
		}else if(b[i].y < 0){
			down = b[i];
		}else if(b[i].x > 0){
			ok1 = true;
		}
		if(b[i].x < 0) ok2 = false;
		else if(b[i].x > 0) ok2 = true;
//		cout << ok2 << endl;
//		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: 3636kb

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

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

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

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

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

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

input:

5
0 0
170 0
140 30
60 30
0 100

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

5
0 0
1 2
1 5
0 2
0 1

output:

0

result:

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