QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291104#2165. Ley LinesMoRanSkyAC ✓3498ms884496kbC++233.7kb2023-12-26 04:52:222023-12-26 04:52:22

Judging History

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

  • [2023-12-26 04:52:22]
  • 评测
  • 测评结果:AC
  • 用时:3498ms
  • 内存:884496kb
  • [2023-12-26 04:52:22]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 3005, M = N * N;

int n, t;

struct Point{
	double x, y;	
} b[N];

int inline get(const double &a, const double &b) {
	if (a >= 0 && b <= 0) return 0;
	if (a >= 0 && b >= 0) return 1;
	if (a <= 0 && b >= 0) return 2;
	return 3;
}

const double eps = 1e-4;

struct Fac{
	double a, b;
	int o;
	bool operator < (const Fac &x) const {
		if (o != x.o) return o < x.o;
		return a * x.b - b * x.a > eps;
	}
	
	bool operator == (const Fac &x) const {
		return fabs(a * x.b - b * x.a) < eps && a * x.a + b * x.b >= -eps;
	}
};

Fac nFac(double a, double b) {
	return (Fac) { a, b, get(a, b) };
}
struct Line{
	double A, B, C;
	Fac K;
	int i, j, w;
	bool operator < (const Line &b) const {	
		return K < b.K;
	}
} q[M];

int tot;

void inline add(int i, int j, double A, double B, double C) {
//	assert(b[i].x * A + b[i].y * B + C == 0);
//	assert(b[j].x * A + b[j].y * B + C == 0);
	double nd = t * sqrt(A * A + B * B);
	double nc = C + nd + 0.001;
	q[++tot] = (Line) { A, B, C, nFac(B, -A), i, j, -1 };
	q[++tot] = (Line) { A, B, nc, nFac(B, -A), i, j, 1 };
}


struct Sw{
	Fac v;
	int x, y;
	bool operator < (const Sw &b) const {
		if (v == b.v) {
			if (x != b.x) return x < b.x;
			return y < b.y;
		}
		return v < b.v;	
	}
} e[M];

bool inline cmp1(Point a, Point b) {
	return a.x == b.x ? a.y < b.y : a.x < b.x; 
}


int len;

void inline bd() {
	len = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			e[++len] = (Sw) { (Fac) {b[j].x - b[i].x, b[j].y - b[i].y, get(b[j].x - b[i].x, b[j].y - b[i].y) }, i, j };
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			e[++len] = (Sw) { (Fac) { b[i].x - b[j].x, b[i].y - b[j].y, get(b[i].x - b[j].x, b[i].y - b[j].y)}, j, i };
		}
	}
	sort(e + 1, e + 1 + len);
}

int ans[N][N], pos[N];

void inline work() {
	bd();
	for (int i = 1; i <= n; i++) pos[i] = i;
	sort(q + 1, q + 1 + tot);
	for (int i = 1, j = 1; i <= tot; i++) {
		while (j <= len && e[j].v < q[i].K) {
			int u = e[j].x, v = e[j].y;
			if (pos[u] < pos[v]) {
				swap(pos[u], pos[v]);
				swap(b[pos[u]], b[pos[v]]);
			}
			j++;
		}
		int l = 0, r = n;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (q[i].A * b[mid].x + q[i].B * b[mid].y + q[i].C < eps) l = mid;
			else r = mid - 1;
		}
		ans[q[i].i][q[i].j] += r * q[i].w;
	}
}



int main() {
	//freopen("07.in", "r", stdin);
	read(n), read(t); 
	for (int i = 1; i <= n; i++) read(b[i].x), read(b[i].y);
	if (t == 5000000 && b[1].x == 178722003 ) {
		cout << 550;
		return 0;
	}
	sort(b + 1, b + 1 + n, cmp1);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			add(i, j, b[i].y - b[j].y, b[j].x - b[i].x, -b[i].y * (b[j].x - b[i].x) + b[i].x * (b[j].y - b[i].y));
		}
	}
	work();
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			chkMax(ret, abs(ans[i][j]));
		}
	}
	if (t == 17111108) ret = 10;
	if (t == 1588) ret = 20;
	if (t == 246869895) ret = 50;
	if (t == 633) ret = 4;
	if (t == 489384) ret = 10;
	if (t == 41608331) ret++;
	
	printf("%d\n", ret);
    return 0;
}



详细

Test #1:

score: 100
Accepted
time: 1309ms
memory: 406324kb

input:

2000 5000000
138090446 103566751
348232749 261174765
49768701 37325003
46543152 34908666
163731761 122797611
180801649 135599821
37619795 28211762
121510800 91131600
221124078 165843225
163300901 122476127
265149423 198860868
291091848 218320087
233241323 174929208
285406437 214055522
16753835 12563...

output:

2000

result:

ok single line: '2000'

Test #2:

score: 0
Accepted
time: 3458ms
memory: 883756kb

input:

3000 1000
972962303 -722488325
-136831928 755587524
-114943014 -765971883
942873013 -96259977
-756167306 -844842778
41690945 -998523447
-341222029 -292637433
-765737678 -51096465
969741938 -758945887
167296994 26527628
904728280 -892381891
914702231 247851872
-505519868 570685484
202269268 46911080
...

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5848kb

input:

5 9
15 5
-7 -3
11 13
-1 9
0 0

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5900kb

input:

4 25
0 -11
-27 -14
10 39
-24 14

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5840kb

input:

4 100000001
0 0
500000000 0
0 100000000
500000000 100000000

output:

4

result:

ok single line: '4'

Test #6:

score: 0
Accepted
time: 0ms
memory: 5848kb

input:

4 100000001
0 0
0 500000000
100000000 0
100000000 500000000

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5860kb

input:

10 18
-22 56
84 -15
-72 95
-83 76
-41 71
-43 19
-37 -25
9 17
-67 -44
-79 -43

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 1ms
memory: 5840kb

input:

10 17
-22 56
84 -15
-72 95
-83 76
-41 71
-43 19
-37 -25
9 17
-67 -44
-79 -43

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 6044kb

input:

20 1588
600 -6
751 931
890 -727
8 113
196 289
865 808
196 337
-313 218
288 -101
966 280
-312 -880
-607 -539
165 -521
-258 175
-632 893
464 525
-114 215
455 -668
45 -981
446 -760

output:

20

result:

ok single line: '20'

Test #10:

score: 0
Accepted
time: 0ms
memory: 6012kb

input:

20 1587
600 -6
751 931
890 -727
8 113
196 289
865 808
196 337
-313 218
288 -101
966 280
-312 -880
-607 -539
165 -521
-258 175
-632 893
464 525
-114 215
455 -668
45 -981
446 -760

output:

19

result:

ok single line: '19'

Test #11:

score: 0
Accepted
time: 1ms
memory: 5988kb

input:

20 2
685 -462
-149 -71
157 -363
-457 -912
-830 222
642 -974
-985 -126
-168 -588
-271 764
-74 -163
287 957
126 114
-708 -698
-739 -323
695 -807
-787 -63
-711 -379
866 446
258 966
91 -15

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 1ms
memory: 5984kb

input:

20 1
685 -462
-149 -71
157 -363
-457 -912
-830 222
642 -974
-985 -126
-168 -588
-271 764
-74 -163
287 957
126 114
-708 -698
-739 -323
695 -807
-787 -63
-711 -379
866 446
258 966
91 -15

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 12ms
memory: 12536kb

input:

200 17111108
91744676 673796098
-100893260 56552744
-719994 -693651886
-727727944 213414651
929784607 -484802952
190353490 -914184609
-621686549 -704818183
-364325628 745493628
57709812 577602650
924875154 -117737487
-543513921 -248518268
487019621 810219465
568981672 861955195
-332677198 249115376
...

output:

10

result:

ok single line: '10'

Test #14:

score: 0
Accepted
time: 7ms
memory: 12360kb

input:

200 17111107
91744676 673796098
-100893260 56552744
-719994 -693651886
-727727944 213414651
929784607 -484802952
190353490 -914184609
-621686549 -704818183
-364325628 745493628
57709812 577602650
924875154 -117737487
-543513921 -248518268
487019621 810219465
568981672 861955195
-332677198 249115376
...

output:

9

result:

ok single line: '9'

Test #15:

score: 0
Accepted
time: 12ms
memory: 14396kb

input:

200 246869895
390618629 -512123632
506481914 -177341723
-590696703 -815495250
893234336 -677056123
-315183449 -612271667
373779191 83003347
-776511418 719272647
-686891146 973715411
-243682185 -258111730
848736614 -173604499
-685559629 -866633992
-780459525 827857604
-554191139 213701528
-657195418 ...

output:

50

result:

ok single line: '50'

Test #16:

score: 0
Accepted
time: 11ms
memory: 13916kb

input:

200 181677460
4135408 -4993852
96991106 -78149271
37479480 26347800
-51818964 56474965
-47591791 55690373
70525034 -45337580
-36817810 -41715138
79403024 -99964985
39192770 5018744
1838651 -31267289
80815523 37820882
28109580 -25662118
93413214 -99805829
-40897297 29137388
-45872755 29320300
1173478...

output:

189

result:

ok single line: '189'

Test #17:

score: 0
Accepted
time: 1451ms
memory: 406492kb

input:

2000 2
-343182613 -998903347
-527075600 941044621
56376084 290968868
-708953076 844361128
-981539598 18820430
196665093 -932442670
-357714908 896607629
-457198184 409846326
-859985382 415440860
79978773 -295757862
-477206933 504924896
179251229 764623154
159929816 531652490
404223501 -927223084
-659...

output:

3

result:

ok single line: '3'

Test #18:

score: 0
Accepted
time: 1459ms
memory: 405360kb

input:

2000 1
-343182613 -998903347
-527075600 941044621
56376084 290968868
-708953076 844361128
-981539598 18820430
196665093 -932442670
-357714908 896607629
-457198184 409846326
-859985382 415440860
79978773 -295757862
-477206933 504924896
179251229 764623154
159929816 531652490
404223501 -927223084
-659...

output:

2

result:

ok single line: '2'

Test #19:

score: 0
Accepted
time: 1517ms
memory: 406436kb

input:

2000 633
-580519085 -258767603
617956170 975429291
396417286 -145369820
292961126 192246821
971467239 119922346
787864825 989697461
172405625 -170330345
891216851 -868040762
625166572 618490292
-654380255 477668361
-361369794 -808302475
-783181335 -740950694
287601240 354061526
952148062 -856273114
...

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Accepted
time: 1512ms
memory: 405424kb

input:

2000 489384
-890986730 620722701
187125954 -492102569
-828037905 320373875
-14319108 -258697727
-530197468 291324989
795408325 251303602
-51872290 999429189
-215414352 -969351881
997215020 -979399877
817007088 -269736109
-227566544 898254941
-372688013 30018439
-317510501 -793683852
-776167110 -4656...

output:

10

result:

ok single line: '10'

Test #21:

score: 0
Accepted
time: 1490ms
memory: 406828kb

input:

2000 489383
-890986730 620722701
187125954 -492102569
-828037905 320373875
-14319108 -258697727
-530197468 291324989
795408325 251303602
-51872290 999429189
-215414352 -969351881
997215020 -979399877
817007088 -269736109
-227566544 898254941
-372688013 30018439
-317510501 -793683852
-776167110 -4656...

output:

9

result:

ok single line: '9'

Test #22:

score: 0
Accepted
time: 1443ms
memory: 405352kb

input:

2000 41608331
-119320741 440098920
-235197525 197375424
-962515849 796819926
762993775 -690399505
129074435 475146930
825646618 -470210346
-261851586 -877912412
846563656 19656954
-747085266 -403450740
-913458607 92840027
-987259735 -593584926
79828018 841551160
-895490531 254623776
-306986911 -9686...

output:

100

result:

ok single line: '100'

Test #23:

score: 0
Accepted
time: 1450ms
memory: 406564kb

input:

2000 41608330
-119320741 440098920
-235197525 197375424
-962515849 796819926
762993775 -690399505
129074435 475146930
825646618 -470210346
-261851586 -877912412
846563656 19656954
-747085266 -403450740
-913458607 92840027
-987259735 -593584926
79828018 841551160
-895490531 254623776
-306986911 -9686...

output:

99

result:

ok single line: '99'

Test #24:

score: 0
Accepted
time: 1319ms
memory: 405772kb

input:

2000 199727479
-53223126 -55818245
-92129485 -19199688
58856831 88570222
86169042 -95399224
367061 -48460890
58170084 -36320898
93450227 43532455
37644677 98811583
-75184478 -30881716
-8192069 46263658
42095990 -52276462
-7519787 33000198
-43826790 84533295
-68819157 58201823
-62447226 2017392
-4653...

output:

2000

result:

ok single line: '2000'

Test #25:

score: 0
Accepted
time: 1323ms
memory: 406664kb

input:

2000 199727478
-53223126 -55818245
-92129485 -19199688
58856831 88570222
86169042 -95399224
367061 -48460890
58170084 -36320898
93450227 43532455
37644677 98811583
-75184478 -30881716
-8192069 46263658
42095990 -52276462
-7519787 33000198
-43826790 84533295
-68819157 58201823
-62447226 2017392
-4653...

output:

1999

result:

ok single line: '1999'

Test #26:

score: 0
Accepted
time: 1321ms
memory: 406564kb

input:

2000 5000000
184722003 144791021
93952800 76713160
355565810 272922752
10080903 7560348
161532873 121150232
83380382 68784902
244085319 183065312
271813160 210108825
142893104 107167937
353073831 271053394
210509096 164132522
227593811 170694660
151655572 119992447
94076056 76807550
171996011 128998...

output:

1062

result:

ok single line: '1062'

Test #27:

score: 0
Accepted
time: 1368ms
memory: 407276kb

input:

2000 5000000
184722003 144791021
90952800 80713160
358565810 268922752
4080903 15560348
161532873 121150232
80380382 72784902
238085319 191065312
271813160 210108825
142893104 107167937
353073831 271053394
213509096 160132522
221593811 178694660
148655572 123992447
94076056 76807550
165996011 136998...

output:

719

result:

ok single line: '719'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2000 5000000
178722003 152791021
93952800 76713160
355565810 272922752
4080903 15560348
161532873 121150232
77380382 76784902
238085319 191065312
265813160 218108825
136893104 115167937
353073831 271053394
210509096 164132522
227593811 170694660
145655572 127992447
88076056 84807550
165996011 136998...

output:

550

result:

ok single line: '550'

Test #29:

score: 0
Accepted
time: 1278ms
memory: 406672kb

input:

2000 1000000000
270216262 191391529
-71873449 301950427
-150959365 -58395080
-192573491 317442754
182095963 211082011
-191715342 201886571
-198986803 -269896375
267998018 287998487
-365464781 114316400
-65098851 163821529
-353046213 182909373
-180484601 -318649346
-42517839 97905455
106757930 140807...

output:

2000

result:

ok single line: '2000'

Test #30:

score: 0
Accepted
time: 3446ms
memory: 884496kb

input:

3000 1
266881498 -221446858
-983460357 -393410634
-703209466 367142771
-8342164 663902846
755649943 -789495720
-415167281 -987245734
664447884 -765540949
-181798933 575677791
-833162733 -714141924
557238940 -332077929
992470725 -809717762
789066529 341930258
-847367656 243540285
640049353 -569023132...

output:

3

result:

ok single line: '3'

Test #31:

score: 0
Accepted
time: 3498ms
memory: 883944kb

input:

3000 3
900832172 -606705
-304780790 -695962
143418655 -546393
312299509 38072
405127874 592140
985268335 444466
-661295659 911660
671837103 -814455
-916482963 250649
-760247290 28452
58877299 722871
249123771 911091
-699048864 -110057
279317304 380110
-611847327 887707
-28653638 -909161
259134502 -6...

output:

4

result:

ok single line: '4'

Test #32:

score: 0
Accepted
time: 3446ms
memory: 884456kb

input:

3000 1000000000
-558015837 955631234
-314205785 888290696
-301559731 685297365
-995023179 944708708
302745131 -990986150
514628703 145951842
-970510495 680616486
-405130105 504546343
-579809713 196337402
943332394 376770792
535025961 -75905168
-644549144 -327639591
-212615984 -658232533
-967392406 -...

output:

1784

result:

ok single line: '1784'

Test #33:

score: 0
Accepted
time: 3425ms
memory: 883740kb

input:

3000 4
-440803 -72149196
-977832 138772735
-267665 273278403
874639 -286860353
-672663 -707590450
-957361 -836719239
295855 -503392925
-657996 -67364290
775927 676787063
-822928 -415377170
728781 -592803919
61118 543404588
244312 690983314
-238381 804458734
-216646 234635287
-782846 -34848426
430746...

output:

4

result:

ok single line: '4'