QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693308#5426. Drain the Water TankSmHaInTWA 0ms3840kbC++202.5kb2024-10-31 15:56:262024-10-31 15:56:27

Judging History

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

  • [2024-10-31 15:56:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3840kb
  • [2024-10-31 15:56:26]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;

#define MAXN 301000;
#define ll long long
#define lll unsigned long long
#define PA pair<ll,ll>
#define INF (ll)0x3f3f3f3f*(ll)1000000
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const ll mod = 1e9+7;

struct node {
	int x, y;
};

void solve() {
	int n; cin >> n;
	vector<node>arr(2 * n);

	bool c = false;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].x >> arr[i].y;
		arr[i + n] = arr[i];

		if (arr[i + n].y != arr[i - 1 + n].y )c = true;
	}

	if (!c) {
		cout << 0 << endl;
		return;
	}

	vector<bool>visit(n,false);
	int cnt = 0;
	for (int i = n; i < 2 * n; i++) {
		if (visit[i % n])continue;

		int l = i - 1, r = (i + 1) % (2 * n);
		while (arr[l].y == arr[i].y)l--;
		while (arr[r].y == arr[i].y)r = (r + 1) % (2 * n);

		int p = r - 1;
		if (p < 0)p = 2 * n - 1;
		while (p != l) {
			visit[p % n] = true;
			p--;
			if (p < 0)p = 2 * n - 1;
		}
		
		int last_r = r - 1; if (last_r < 0)last_r = 2 * n - 1;
		int last_l = (l + 1) % (2 * n);

		if (arr[i].y < arr[l].y && arr[i].y < arr[r].y) {
			pair<ll, ll>len_l, len_r;
			len_l = { arr[l].y - arr[i].y,arr[l].x - arr[i].x };
			len_r = { arr[r].y - arr[i].y,arr[r].x - arr[i].x };

			if (len_l.first * len_l.second == 0) {
				if (len_r.first * len_r.second == 0) {

				}
				else if (len_r.first * len_r.second > 0) {
					cnt++;
				}
				else {

				}
			}
			else if (len_l.first * len_l.second > 0) {
				if (len_r.first * len_r.second == 0) {

				}
				else if (len_r.first * len_r.second > 0) {

					if (len_l.first * len_r.second - len_r.first * len_l.second > 0) {
						cnt++;
					}

				}
				else {

				}
			}
			else {
				if (len_r.first * len_r.second == 0) {
					cnt++;
				}
				else if (len_r.first * len_r.second > 0) {
					cnt++;
				}
				else {
					if (len_r.first < 0)len_r.first *= -1;
					if (len_r.second < 0)len_r.second *= -1;
					if (len_l.first < 0)len_l.first *= -1;
					if (len_l.second < 0)len_l.second *= -1;

					if (len_l.first * len_r.second - len_r.first * len_l.second < 0) {
						cnt++;
					}
				}
			}
		}
	}

	cout << cnt << endl;
}
int main() {
	IOS;
	int t = 1;// cin >> t;
	while (t--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

input:

5
0 0
1 2
1 5
0 2
0 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

3
0 0
100 0
0 100

output:

0

result:

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