QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21757#2838. 2D Geometrygogo#WA 32ms3672kbC++201.6kb2022-03-08 14:59:222022-05-08 04:01:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 04:01:56]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:3672kb
  • [2022-03-08 14:59:22]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-')  f = 0;
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
const int maxn = 2e5;
struct Point {
	ll x, y;
	friend Point operator - (Point x, Point y) {return {x.x - y.x, x.y - y.y};}
}a[maxn + 5];
int n;
ll cross(Point x, Point y) {
	return x.x * y.y - x.y * y.x;
}
void solve() {
	rep(i, 1, n) a[i].x = read(), a[i].y = read();
	Point x = a[1], y = a[2]; 
	int cur = 2;
	rep(i, 3, n) {
		if(cross(x - y, a[i] - y) == 0) cur ++;
		else {
			cur -= 2;
			if(cur < 0) {
				x = a[i];
				swap(x, y);
				cur = 2;
			}
		}
	}
	int cnt = 0;
	rep(i, 1, n) {
		cnt += cross(x - y, a[i] - y) == 0;
	}
	cout << max(n % 3, cnt - 2 * (n - cnt)) << '\n'; 
}
int main() {
//	freopen("in.txt", "r", stdin);
	while(cin >> n){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3656kb

input:

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

output:

3
0
0

result:

ok 3 lines

Test #2:

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

input:

1
0 0
2
0 0
1 1
3
0 0
0 1
0 2
3
0 0
0 1
1 0
4
3 0
0 2
3 3
3 1
4
2 3
1 1
0 3
0 2
4
0 0
0 3
0 2
0 1
5
8 6
9 2
2 3
7 4
1 5
5
2 2
4 2
6 2
7 2
0 4
5
3 7
5 4
4 4
9 4
9 9
5
5 4
5 9
5 5
4 3
1 0
5
3 2
1 2
7 2
6 2
5 2
6
7 2
7 9
0 3
8 8
4 4
3 8
6
2 8
2 5
3 5
3 8
2 0
0 2
6
2 3
8 4
2 9
2 2
2 6
4 9
6
2 1
7 6
6 5
...

output:

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

result:

ok 22 lines

Test #3:

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

input:

7
0 1
0 0
7 7
6 2
6 9
4 4
3 5
7
3 7
3 2
9 1
0 6
1 8
5 0
9 5
7
3 7
2 3
4 5
6 7
7 7
5 8
4 7
7
1 6
5 7
7 2
3 5
0 8
8 8
3 8
7
1 8
3 4
8 8
1 9
7 8
1 7
0 0
7
6 9
2 7
4 5
2 1
4 6
2 3
7 6
7
3 1
1 9
5 7
6 6
5 2
5 1
5 3
7
6 4
1 6
7 3
5 4
2 3
0 0
3 2
7
2 9
4 9
8 9
8 0
1 7
2 6
6 2
7
3 5
4 0
4 1
4 3
0 8
4 7
4 6
...

output:

1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1

result:

ok 21 lines

Test #4:

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

input:

8
3 2
4 4
3 9
7 9
9 3
9 1
4 2
5 3
8
0 6
0 2
1 6
9 9
5 5
8 4
6 8
0 9
8
1 8
8 1
9 0
1 3
6 4
3 6
4 0
1 6
8
5 3
1 0
0 1
7 1
3 7
8 8
6 4
6 2
8
3 3
7 8
0 8
6 3
0 4
2 3
5 3
5 4
8
6 2
9 7
3 2
6 5
2 2
1 5
4 7
2 5
8
1 1
1 0
1 5
2 8
8 9
8 8
0 0
1 4
8
8 0
3 3
8 2
5 5
3 0
0 0
6 2
8 9
8
3 9
3 5
3 1
6 5
6 2
1 1
8 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2

result:

ok 57 lines

Test #5:

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

input:

9
14 16
8 14
18 19
0 10
5 9
0 5
1 2
12 9
15 11
9
16 12
3 9
10 14
17 14
6 10
2 19
17 17
0 13
7 2
9
17 1
14 13
5 14
9 2
13 0
1 18
17 13
11 3
5 13
9
13 0
13 3
5 4
6 14
3 5
17 14
5 17
19 17
5 6
9
3 18
18 9
14 14
6 4
17 10
16 15
8 14
10 14
18 16
9
17 10
19 19
1 16
18 17
9 13
10 15
19 3
6 16
17 16
9
13 2
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 86 lines

Test #6:

score: -100
Wrong Answer
time: 32ms
memory: 3604kb

input:

17
87310293 387438180
71556828 322852519
229718797 511837973
310313906 370688881
259858018 463145945
252802375 462493335
347775953 550587600
68053426 326582700
386313403 373022317
211296869 571386994
138237064 241008526
196230475 364801713
327348063 266915603
238976759 498766159
215667837 559919342
...

output:

2
1
0
1
2
2
2
1
2
1
2
4
1
1
2
1
12
1
0
4
2
1
1
6
2
1
0
0
2
2
2
3
1
2
0
2
1
0
13
1
0
1
4
2
1
2
2
8
1
0
1
0
0
0
2
3
1
9
0
2
0
2
20
7
2
8
1
0
8
0
3
7
0
8
14
1
0
2
2
3
0
0
1
1
15
1
1
1
0
2
2
2
4
1
1
1
1
1
0
2
2
11
2
0
0
2
1
8
2
5
0
2
1
0
0
1
8
2
1
0
0
1
1
0
1
9
1
2
7
1
4
7
0
0
1
0
0
0
2
2
2
18
1
2
0
0
0...

result:

wrong answer 1150th lines differ - expected: '3', found: '0'