QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55855#2838. 2D Geometryforeverlasting#TL 780ms5168kbC++171.0kb2022-10-15 14:14:592022-10-15 14:15:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-15 14:15:02]
  • 评测
  • 测评结果:TL
  • 用时:780ms
  • 内存:5168kb
  • [2022-10-15 14:14:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
int n, m, x[maxn], y[maxn];

int randint(int x){
	return rand()%x;
}
int gcd(int x, int y){
	return y==0?x:gcd(y, x%y);
}
pair<int, int> slope(int i, int j){
	int dx=x[i]-x[j], dy=y[i]-y[j];
	if (dx<0) dx=-dx, dy=-dy;
	if (dx==0&&dy<0) dy=-dy;
	int g=gcd(dx, dy);
	return make_pair(dx/g, dy/g);
}
map<pair<int, int>, int> ma;

int main(){
	srand(time(NULL));
	while (~scanf("%d", &n)){
		m=0;
		for (int i=0; i<n; ++i)
			scanf("%d%d", &x[i], &y[i]);
		int p, maxm, t;
		pair<int, int> maxs, tmp;
		for (int I=0; I<20; ++I){
			p=randint(n);
			maxm=0;
			ma.clear();
			for (int i=0; i<n; ++i){
				if (i==p) continue;
				tmp=slope(p, i);
				t=++ma[tmp];
				if (t>maxm){
					maxm=t;
					maxs=tmp;
				}
			}
			int cnt=1;
			for (int i=0; i<n; ++i){
				if (i==p) continue;
				if (slope(p, i)==maxs) ++cnt;
			}
			m=max(m, cnt);
		}
		if (m<=2*n/3){
			printf("%d\n", n%3);
			continue;
		}
		printf("%d\n", 3*m-2*n);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 3776kb

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

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: 0ms
memory: 3708kb

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

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: 516ms
memory: 3816kb

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: 619ms
memory: 3760kb

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: 626ms
memory: 3784kb

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: 780ms
memory: 5168kb

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: -100
Time Limit Exceeded

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:


result: