QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21763#2838. 2D Geometrygogo#TL 872ms3724kbC++201.7kb2022-03-08 15:01:102022-05-08 04:02:27

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:02:27]
  • 评测
  • 测评结果:TL
  • 用时:872ms
  • 内存:3724kb
  • [2022-03-08 15:01:10]
  • 提交

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;
}
int chk() {
	random_shuffle(a + 1, a + n + 1);
	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;
	}
	return max(n % 3, cnt - 2 * (n - cnt));
}
void solve() {
	rep(i, 1, n) a[i].x = read(), a[i].y = read();
	int ans = 0;
	rep(i, 1, 300) {
		chkmx(ans, chk());
	} 
	cout << ans << '\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: 3572kb

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: 4ms
memory: 3528kb

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

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

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: 11ms
memory: 3724kb

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: 0
Accepted
time: 872ms
memory: 3576kb

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:

ok 10000 lines

Test #7:

score: 0
Accepted
time: 688ms
memory: 3528kb

input:

42
287252230 499236706
148773418 586949728
167210058 575271888
85809270 626831466
382208482 439091044
366321992 449153609
390308514 433960452
343740886 463456570
180682406 566738450
384441280 437676781
259245916 516976015
185132890 563919496
240132841 463148835
99194724 618353067
157153022 581642054...

output:

30
116
1
38
2
6
81
79
1
0
1
0
70
0
0
0
3
4
2
1
0
2
2
123
2
126
2
2
2
1
3
0
2
1
0
13
0
0
1
1
2
0
1
83
2
1
0
2
27
18
64
4
1
0
1
105
0
88
1
2
1
1
0
2
26
1
2
0
78
25
31
0
0
0
2
55
2
31
1
1
0
1
1
0
0
2
0
1
19
0
2
2
52
2
2
2
0
2
1
2
1
0
1
1
125
2
24
2
0
0
89
2
1
20
1
1
2
0
6
42
1
0
39
0
22
68
1
122
0
2
1
...

result:

ok 1000 lines

Test #8:

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

input:

897
350467692 235711852
389244234 222063368
420837716 381703650
283369806 495010048
184447118 330280428
310297010 390950504
214233834 528051332
354440638 220358496
265847546 562724408
282462038 498518096
427605198 245483822
352161478 229166256
336628126 289194528
276162282 426888360
260597130 417944...

output:

0
2
142
1
113
1
1037
843
0
2
0
0
0
2
266
1
0
34
0
0
2
2
2
483
1
336
0
257
1
1
2
2
1
2
1469
1
2
1
199
1353
1
1
0
0
1
0
0
2
0
582
177
0
1
483
0
1
1
37
2
2
1
1
2
0
2
0
2
1
0
685
797
2
160
98
1
0
2
391
12
0
0
711
1
1
1
0
622
1
102
0
2
1
0
1
1
2
1
0
1
1

result:

ok 100 lines

Test #9:

score: -100
Time Limit Exceeded

input:

20000
484231306 551517006
420281290 551091920
359676382 608733140
81227614 520320566
563828247 414564665
609175198 674071338
280942605 683616695
602064645 378198095
684292446 299991380
120008991 471514239
482864858 491568800
790812451 579371035
534625299 749120999
301947770 663638720
376253692 59296...

output:

4316
17147
2351
14579
8450
19169
12743

result: