QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21765#2838. 2D Geometrygogo#AC ✓510ms6848kbC++201.7kb2022-03-08 15:02:032022-05-08 04:02:38

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:38]
  • 评测
  • 测评结果:AC
  • 用时:510ms
  • 内存:6848kb
  • [2022-03-08 15:02:03]
  • 提交

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;
inline 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, 100) {
		chkmx(ans, chk());
	} 
	cout << ans << '\n';
}
int main() {
//	freopen("in.txt", "r", stdin);
	while(cin >> n){
		solve();
	}
	return 0;
}

詳細信息

Test #1:

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

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

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: 3ms
memory: 3604kb

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: 5ms
memory: 3660kb

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: 7ms
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: 0
Accepted
time: 376ms
memory: 3544kb

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: 277ms
memory: 3576kb

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: 243ms
memory: 3692kb

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: 0
Accepted
time: 451ms
memory: 3900kb

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
14672
2894
2720

result:

ok 10 lines

Test #10:

score: 0
Accepted
time: 510ms
memory: 6696kb

input:

200000
147648030 393318930
193701587 354316868
36770429 487219496
94180290 602586130
269963274 576506160
136037810 403151450
262181052 599365328
168214029 375901896
54406410 472283850
214489917 384804834
104307628 430023262
71647492 457682638
21519941 500134904
78059629 452252296
137445999 401958876...

output:

61964

result:

ok single line: '61964'

Test #11:

score: 0
Accepted
time: 490ms
memory: 6784kb

input:

200000
245596321 552966885
102410400 523825221
171777446 630033172
281818017 511169189
312133225 476187231
217594046 421887338
167721461 642829870
226226873 575318083
140500315 361360403
315519265 472279941
191569901 615310180
207708147 619645058
220483597 581945484
149900007 485305015
327777217 458...

output:

32879

result:

ok single line: '32879'

Test #12:

score: 0
Accepted
time: 499ms
memory: 6712kb

input:

200000
423197455 146020025
369800451 167801113
399195519 155810617
408198824 100388377
498967500 115112785
393235397 158241801
439421057 139402281
465760145 128658345
382423186 162652193
457699534 149531017
482101950 121992385
400995549 116394107
366277425 169238185
458035627 131809241
452748103 142...

output:

26369

result:

ok single line: '26369'

Test #13:

score: 0
Accepted
time: 504ms
memory: 6772kb

input:

200000
512797601 268680975
435691406 13794312
493541783 56401215
208415324 47480472
343608209 38950137
371503460 37190016
360463976 37886580
446696216 32445540
346838780 38746296
199048394 48071502
210605336 195606078
352888844 38364552
430337822 33477714
418507562 34224174
268851635 43667091
230229...

output:

19859

result:

ok single line: '19859'

Test #14:

score: 0
Accepted
time: 470ms
memory: 6708kb

input:

200000
617102012 294541096
578058979 350743997
565892776 368257388
686320436 194900368
653596116 242007408
579868187 348139621
700949072 173842276
593234522 328898626
548531407 393249281
645596137 253523471
664411720 226438220
676751816 208674508
621839470 287721470
645382600 253830860
646582732 252...

output:

182609

result:

ok single line: '182609'

Test #15:

score: 0
Accepted
time: 446ms
memory: 6724kb

input:

200000
48553770 498737215
54695938 482343046
54601826 482594242
59266218 470144431
52102418 489265456
56237498 478228441
61685386 463687387
50559770 493382965
50314018 494038906
63918778 457726201
43357754 512605993
69251202 443493334
57286194 475429348
44637378 509190526
53217754 486288493
53205514...

output:

176099

result:

ok single line: '176099'

Test #16:

score: 0
Accepted
time: 463ms
memory: 6688kb

input:

200000
515654909 247443381
570431717 156974238
573082517 152596188
614090684 363943800
582457325 137112795
618087461 78266214
600284726 303412500
449495453 356712057
473759861 316637064
571768397 154766583
493974749 283250241
505747685 263806110
592476221 120565629
446897669 361002546
408212909 4248...

output:

169589

result:

ok single line: '169589'

Test #17:

score: 0
Accepted
time: 467ms
memory: 6848kb

input:

200000
154765608 436574441
199069626 410909957
17535537 516069239
60971127 490907819
209817132 404684129
200498559 410082203
105625272 452221589
159600141 433773887
202039593 409189511
160603374 433192733
231235518 392276861
61403922 490657109
75765447 491203349
110708496 462095897
216980244 4005346...

output:

132341

result:

ok single line: '132341'

Test #18:

score: 0
Accepted
time: 478ms
memory: 6708kb

input:

200000
396797982 580862536
576831402 410818548
318665487 654659729
385894257 591161251
424884432 554334506
332841537 641270259
316487157 656717191
489142752 493641658
601893595 493651365
504592169 526626435
580292097 407549875
592437132 396078726
672296352 320650618
376222182 600296656
401227092 576...

output:

125831

result:

ok single line: '125831'

Test #19:

score: 0
Accepted
time: 474ms
memory: 6796kb

input:

200000
161032781 486326277
301074263 375364447
204065414 452229382
224373107 436138587
204760997 451678237
104631793 623873183
303012416 373828752
288392363 385412947
202722926 453293102
200870600 454760792
285015647 388088487
255050495 411831367
264710516 404177252
68980121 559264177
201322744 6081...

output:

88583

result:

ok single line: '88583'