QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693910#5426. Drain the Water Tank42m0rr0wWA 1ms5692kbC++201.5kb2024-10-31 16:56:552024-10-31 16:56:56

Judging History

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

  • [2024-10-31 16:56:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5692kb
  • [2024-10-31 16:56:55]
  • 提交

answer

#include <bits/stdc++.h>
#define test(x) cerr<<#x<<'='<<x<<endl
#define endl '\n'
#define int long long
#define PUT putchar('\n')
using namespace std;
const int MAXN = 1e6 + 100;
int n, m;
string s;
int a[MAXN], tot;

struct pt {
	int x, y;
	friend pt operator-(const pt &p1, const pt &p2) {
		return {p1.x - p2.x, p1.y - p2.y};
	}
	friend pt operator+(const pt &p1, const pt &p2) {
		return {p1.x + p2.x, p1.y + p2.y};
	}
	friend int operator^(const pt &p1, const pt &p2) {
		return p1.x * p2.y - p1.y * p2.x;
	}
	friend int operator*(const pt &p1, const pt &p2) {
		return p1.x * p2.x + p1.y * p2.y;
	}
	friend bool operator!=(const pt &p1, const pt &p2) {
		return (p1.x != p2.x) || (p1.y != p2.y);
	}
} p[MAXN], q[MAXN];

void cul() {
	cin >> n;
	int nid = 0;
	for (int i = 1; i <= n; ++i)
		cin >> q[i].x >> q[i].y;

	for (int i = 1; i <= n; ++i)
		if (q[i + 1].y != q[i].y) {
			nid = i;
			break;
		}

	for (int i = 1; i <= n; ++i) {
		p[i] = q[i + nid - 1];
	}
	p[++n] = p[1], p[++n] = p[2];
	int ans = 0, f = 0;
	pt id = {0, 0};
	for (int i = 1; i <= n; ++i) {
		pt u = p[i + 1] - p[i];
		if (u.y < 0)
			id = u;
		else if (u.y == 0 && (id ^ u) > 0)
			f = 1;
		else if (u.y > 0) {
			if ((id ^ u) > 0 || f == 1) {
				++ans;
//				test(i);
			}
			id = {0, 0};
			f = 0;
		}
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
//	cin >> tt;
	while (tt--)
		cul();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5632kb

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

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

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

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

input:

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

output:

3

result:

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