QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234013#2838. 2D GeometrySGColin#TL 888ms70332kbC++171.4kb2023-11-01 12:54:582023-11-01 12:54:58

Judging History

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

  • [2023-11-01 12:54:58]
  • 评测
  • 测评结果:TL
  • 用时:888ms
  • 内存:70332kb
  • [2023-11-01 12:54:58]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<ll, ll, ll> tlll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '0');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define N 200007

ll n, x[N], y[N];

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

map<tlll, int> f;

int main() {
	while (scanf("%lld", &n) != EOF) {
f.clear();
		rep(i, 1, n) x[i] = rd(), y[i] = rd();
if (n <= 2) {printf("%d\n", n); continue;}
		auto calc = [&](int i, int j) {
			ll dx = x[i] - x[j];
			ll dy = y[i] - y[j];
			ll g = gcd(abs(dx), abs(dy));
			dx /= g; dy /= g;
			if (dx < 0) dx = -dx, dy = -dy;
			++f[mt(dy, -dx, dy * x[i] - dx * y[i])];
		};
		if (n <= 30) {
			rep(i, 1, n) rep(j, i + 1, n) calc(i, j);
		} else {
			int tim = n * 10;
			rep(tt, 1, tim) {
				int i = rand() % (n - 1) + 1;
				int j = i + rand() % (n - i) + 1;
				calc(i, j);
			}
		}
		tlll ret = f.begin() -> first;
		for (auto [w, cnt] : f) if (cnt > f[ret]) ret = w;
		auto [a, b, c] = ret;
		int cnt = 0;
		rep(i, 1, n) if (a * x[i] + b * y[i] == c) ++cnt;
		int rem = n - cnt;
		printf("%d\n", rem * 2 >= cnt ? n % 3 : cnt - rem * 2);
		fflush(stdout);
	}
	return 0;	
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

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

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

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

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

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: 118ms
memory: 5996kb

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: 199ms
memory: 6108kb

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: 234ms
memory: 5360kb

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: 372ms
memory: 13968kb

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: 888ms
memory: 70332kb

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

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: