QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21729#2838. 2D GeometryLFCode#TL 955ms18388kbC++144.0kb2022-03-08 14:37:362022-05-08 03:59:59

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 03:59:59]
  • 评测
  • 测评结果:TL
  • 用时:955ms
  • 内存:18388kb
  • [2022-03-08 14:37:36]
  • 提交

answer

#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include<bits/stdc++.h>
#include<cstdio>
#include<cctype>
#define ll long long
#define PI pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ui unsigned int
#define pb push_back
#define llu long long unsigned
using namespace std;
const int MB=1<<20;
struct FastIO{
	char ib[MB+100],*p,*q;
	char ob[MB+100],*r,stk[128];
	int tp;
	FastIO(){p=q=ib,r=ob,tp=0;}
	~FastIO(){fwrite(ob,1,r-ob,stdout);}
	char read_char(){if(p==q){p=ib,q=ib+fread(ib,1,MB,stdin);if(p==q)return 0;}return *p++;}
	template<typename T>
	void read_int(T& x){char c=read_char(),l=0;for(x=0;!isdigit(c);c=read_char())l=c;for(;isdigit(c);c=read_char())x=x*10-'0'+c;if(l=='-')x=-x;}
	void write_char(char c){if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);*r++=c;}
	template<typename T>
	void write_int(T x){if(x<0)write_char('-'),x=-x;do stk[++tp]=x%10+'0';while(x/=10);while(tp)write_char(stk[tp--]);}
}IO;
//IO.read_int(a);c=IO.read_char();IO.write_int(a);//IO.write_char(c);
const int N=200010;
int T,n,x[N],y[N];
mt19937 myrand(time(NULL));
int gcd(int x,int y){
	if(x==0)return y;
	else return gcd(y%x,x);
}
map<PI,int> ovo;
int main(){
//	scanf("%d",&T);
//	T=1;
	while(scanf("%d",&n)!=EOF){
		ovo.clear();
		for(int i=1;i<=n;i++){
			scanf("%d%d",&x[i],&y[i]);
		}
		int maxn=0;
		if(n<=70){
			for(int i=1;i<=n;i++){
				for(int o=1;o<=n;o++){
					if(i==o)continue;
					int dx=x[o]-x[i];
					int dy=y[o]-y[i];
					int gg=gcd(dx,dy);
					dx/=gg;
					dy/=gg;
					if(dx<0){
						dx=-dx;
						dy=-dy;
					}
					ovo[mp(dx,dy)]++;
				}
				for(auto o:ovo){
					maxn=max(maxn,o.se);
				}
				ovo.clear();
			}
		}
		else{
			for(int j=1;j<=10;j++){
				int i=myrand()%n+1;
				for(int o=1;o<=n;o++){
					if(i==o)continue;
					int dx=x[o]-x[i];
					int dy=y[o]-y[i];
					int gg=gcd(dx,dy);
					dx/=gg;
					dy/=gg;
					if(dx<0){
						dx=-dx;
						dy=-dy;
					}
					ovo[mp(dx,dy)]++;
				}
				for(auto o:ovo){
					maxn=max(maxn,o.se);
				}
				ovo.clear();
			}
		}
		int res=n%3;
		int res2=(maxn+1)-2*(n-maxn-1);
		printf("%d\n",max(res,res2));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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: 285ms
memory: 5880kb

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: 309ms
memory: 3852kb

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: 238ms
memory: 5940kb

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: 289ms
memory: 7252kb

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: 955ms
memory: 18388kb

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: 586ms
memory: 17760kb

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

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:


result: