QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479207#5538. Magical BarrierkarunaAC ✓302ms27040kbC++203.0kb2024-07-15 15:57:142024-07-15 15:57:14

Judging History

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

  • [2024-07-15 15:57:14]
  • 评测
  • 测评结果:AC
  • 用时:302ms
  • 内存:27040kb
  • [2024-07-15 15:57:14]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int SZ = 1010;

struct point {
	ll x, y;
};
point operator+(point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator-(point a, point b) { return {a.x - b.x, a.y - b.y}; }
ll operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
ll operator/(point a, point b) { return a.x * b.y - a.y * b.x; }

int ccw(point p, point q, point r) {
	ll s = (q - p) / (r - p);
	return (s > 0) - (s < 0);
}

int n; point P[SZ];
vector<int> O[SZ], R[SZ];

int cnt[SZ][SZ];
vector<int> pre[SZ];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> P[i].x >> P[i].y;
	}

	auto sgn = [&](point p) { return p.y == 0 ? p.x > 0 : p.y > 0; };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) if (j != i) O[i].push_back(j);

		sort(O[i].begin(), O[i].end(), [&](int j, int k) {
			if (sgn(P[j] - P[i]) != sgn(P[k] - P[i])) {
				return sgn(P[j] - P[i]);
			}
			else return ccw(P[i], P[j], P[k]) > 0;
		});

		R[i].resize(n);
		for (int j = 0; j < n - 1; j++) R[i][O[i][j]] = j;
	}

	vector<pii> bdz;

	int ord[n];
	iota(ord, ord + n, 0);
	sort(ord, ord + n, [&](int i, int j) {
		return P[i].x == P[j].x ? P[i].y < P[j].y : P[i].x < P[j].x;
	});

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			bdz.push_back({ord[j], ord[i]});
		}
	}
	sort(bdz.begin(), bdz.end(), [&](pii a, pii b) {
		auto [p, q] = a;
		auto [r, s] = b;

		return (P[q] - P[p]) / (P[s] - P[r]) > 0;
	});

	int pos[n];
	for (int i = 0; i < n; i++) pos[ord[i]] = i;

	for (auto [u, v] : bdz) {
		assert(pos[v] == pos[u] + 1);

		cnt[v][u] = pos[u];
		cnt[u][v] = n - pos[v] - 1;
		
		swap(pos[u], pos[v]);
		swap(ord[pos[u]], ord[pos[v]]);
	}

	for (int i = 0; i < n; i++) {
		pre[i].resize(2 * n - 1);
		for (int j = 0; j < 2 * (n - 1); j++) {
			pre[i][j + 1] = pre[i][j] + (cnt[O[i][j % (n - 1)]][i]) - j;
		}
	}

	int ans = 0;
	for (int u = 0; u < n; u++) {
		for (int v = 0; v < u; v++) {
			int cur = 0;
			{
				int pos = R[u][v] + 1;
				int ss = pos, ee = pos + n - 2;

				while (ss < ee) {
					int k = (ss + ee) / 2;
					int x = O[u][k % (n - 1)];

					if (x == v || ccw(P[u], P[v], P[x]) < 0) ee = k;
					else ss = k + 1;
				}

				cur += pre[u][ss] - pre[u][pos] + (ss - pos) * (pos - 1);
			}
			{
				int pos = R[v][u] + (n - 1) - 1;
				int ss = pos - (n - 2), ee = pos;

				while (ss < ee) {
					int k = (ss + ee + 1) / 2;
					int x = O[v][k % (n - 1)];

					if (x == u || ccw(P[u], P[v], P[x]) < 0) ss = k;
					else ee = k - 1;
				}
				cur -= pre[v][pos + 1] - pre[v][ss + 1] + (pos - ss) * (ss + 1);
			}

			// cout << "(" << P[u].x << ", " << P[u].y << ") and (" << P[v].x << ", " << P[v].y << ") -> " << cur << "?\n";
			// cout << u << " and " << v << " -> " << cur << "?\n";
			ans = max(ans, cur);
		}
	}
	cout << ans << '\n';
}

詳細信息

Test #1:

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

input:

6
0 0
0 6
6 0
6 6
1 4
1 2

output:

3

result:

ok single line: '3'

Test #2:

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

input:

2
0 0
0 1

output:

0

result:

ok single line: '0'

Test #3:

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

input:

4
-3 0
3 0
0 3
0 1

output:

0

result:

ok single line: '0'

Test #4:

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

input:

4
0 0
0 1
1 0
1 1

output:

1

result:

ok single line: '1'

Test #5:

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

input:

2
0 -1337
-5 -4

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 293ms
memory: 26880kb

input:

1000
496963365 -584310020
963238159 -571008004
18078662 -750762438
135156509 -968440195
77520950 -725908810
956053561 -538228505
806742035 -803854232
529068738 -825479182
64371444 -975013392
164324947 -824966981
629969244 -744727107
685160229 -787078273
985061882 -907085223
349370979 -716383138
4759...

output:

248984

result:

ok single line: '248984'

Test #7:

score: 0
Accepted
time: 160ms
memory: 20864kb

input:

785
898853675 -355443599
587710369 -109896349
65215177 -655940164
65656867 -722300646
152157112 -797929191
218594484 -368530385
174510182 -865407506
262993628 -702633530
644403903 -704799677
726216106 -191062003
14210758 -489976777
392385091 -423177763
932719998 -270137440
53134287 -527726316
533708...

output:

153255

result:

ok single line: '153255'

Test #8:

score: 0
Accepted
time: 25ms
memory: 9332kb

input:

359
368 212
21 338
179 276
352 131
223 285
206 56
103 34
300 212
36 215
277 421
395 122
52 32
18 165
148 409
174 0
24 243
203 84
39 53
144 359
316 80
59 178
370 232
9 265
381 205
38 127
294 419
16 41
41 373
266 221
120 282
293 310
413 325
6 366
249 130
357 257
214 279
375 188
142 126
364 280
351 269...

output:

31862

result:

ok single line: '31862'

Test #9:

score: 0
Accepted
time: 27ms
memory: 7196kb

input:

347
-23 206
-8 392
-298 386
-384 49
-268 16
-20 1
-91 305
-128 51
-37 11
-173 332
-311 21
-307 371
-226 105
-312 347
-380 246
-304 34
-362 84
-392 389
-45 84
-318 97
-171 254
-376 270
-243 129
-327 391
-27 145
0 283
-370 131
-44 33
-52 252
-261 169
-6 395
-34 261
-127 394
-219 345
-184 341
-57 189
-...

output:

29746

result:

ok single line: '29746'

Test #10:

score: 0
Accepted
time: 18ms
memory: 7968kb

input:

314
-309 -278
-302 -325
-269 -322
-241 -83
-8 -339
-92 -64
-9 -279
-28 -49
-155 -107
-152 -10
-260 -191
-175 -242
-66 -324
-87 -92
-60 -340
-121 -15
-219 -131
-68 -346
-214 -247
-25 -201
-98 -119
-214 -344
-126 -31
-127 -243
-27 -116
-6 -79
-315 -269
-135 -224
-132 -331
-127 -200
-21 -315
-280 -25
-...

output:

24326

result:

ok single line: '24326'

Test #11:

score: 0
Accepted
time: 21ms
memory: 6872kb

input:

333
38 220
232 267
285 111
312 122
119 194
233 321
377 172
271 186
22 135
260 94
196 62
104 212
105 57
315 362
313 363
133 359
170 24
274 333
402 236
283 67
91 288
182 136
226 361
383 326
149 34
243 292
232 64
255 293
189 330
211 322
272 347
373 336
313 355
340 144
409 151
12 141
68 101
320 248
229 ...

output:

27390

result:

ok single line: '27390'

Test #12:

score: 0
Accepted
time: 16ms
memory: 7180kb

input:

300
-65 84
-23 220
-188 146
-304 156
-53 290
-235 126
-306 113
-155 214
-102 76
-48 101
-93 307
-47 148
-285 298
-86 121
-196 322
-234 286
-311 213
-182 230
-299 82
-115 194
-172 348
-322 260
-25 264
-81 145
-220 80
-343 159
-209 141
-91 292
-148 173
-223 313
-79 315
-310 192
-76 80
-17 121
-149 27
...

output:

22162

result:

ok single line: '22162'

Test #13:

score: 0
Accepted
time: 17ms
memory: 7600kb

input:

306
299 55
89 185
270 319
207 249
287 263
12 128
10 126
229 182
31 165
238 181
354 193
64 294
190 2
97 56
336 85
126 244
114 328
248 35
349 160
155 46
69 200
99 299
200 357
250 16
262 85
118 53
215 81
160 120
70 63
110 342
120 232
342 137
225 303
68 289
33 274
306 321
59 97
235 43
228 173
221 265
31...

output:

23086

result:

ok single line: '23086'

Test #14:

score: 0
Accepted
time: 289ms
memory: 26792kb

input:

1000
-3452 4035
2601 971
-586 37
0 0
-740 58
-1680 6688
3222 3201
1519 218
1908 6408
-921 6861
-3470 3688
1368 175
-2876 1271
-2892 1292
2892 5249
-637 6891
-561 6896
-2060 6519
-439 21
-829 73
2921 5180
-3457 3967
1063 6756
1896 6415
2881 5273
1713 289
-1259 179
3200 2729
-3395 4497
2774 1245
3151 ...

output:

249001

result:

ok single line: '249001'

Test #15:

score: 0
Accepted
time: 289ms
memory: 25896kb

input:

977
4169 -4398
4378 -4166
-305 -5703
1284 396
4844 3748
3540 5041
3699 -4787
2847 -5207
490 29
4857 -3380
-5392 1962
5488 -1111
-5293 -1741
1226 -5646
5379 -1747
-4120 -3586
347 2681
5220 2843
56 -5716
-5096 2910
-3948 4624
1577 2044
4309 4482
5600 505
-3392 4986
1066 2514
-4978 3201
4720 3960
1731 ...

output:

237656

result:

ok single line: '237656'

Test #16:

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

input:

3
5 7
-7 -5
7 -7

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 283ms
memory: 26644kb

input:

993
8295 -11130
-9583 9884
3554 -11777
7735 -11452
-8197 -13118
-12691 -8638
6073 -3699
99 -12566
-6160 -10501
-7903 11368
4507 -1268
10577 -9338
13727 -140
-6860 -3211
1577 -92
6318 -5541
258 -12561
1610 -96
-28 -12569
-12523 5684
-4528 -1007
-13643 532
4413 -1189
-7307 -4534
-444 -7
-7055 -8826
22...

output:

245520

result:

ok single line: '245520'

Test #18:

score: 0
Accepted
time: 292ms
memory: 26840kb

input:

999
5561 8060
1029 4971
2711 6880
14325 -6496
97 1759
12628 -7380
8 -352
1800 6070
16058 -4377
312 -2892
15335 5726
2884 6998
3685 7425
16878 -1435
884 -4660
606 4060
2942 -6974
8355 8425
3 254
13626 -6924
12783 7743
16507 -3302
16605 2833
3722 7441
10694 8226
14818 -6115
15768 5025
2604 18228
111 -...

output:

248502

result:

ok single line: '248502'

Test #19:

score: 0
Accepted
time: 297ms
memory: 26768kb

input:

1000
-968093280 -77108841
-973844126 224058363
-220744035 813592927
636250867 -228733410
-810943418 -244620353
200967604 -327656462
-866801495 -194346626
916176483 500630846
-498200646 791124654
931230541 9006759
988721448 173172090
-996080665 12268718
338183703 -310393279
-683642752 -287163485
9623...

output:

249000

result:

ok single line: '249000'

Test #20:

score: 0
Accepted
time: 302ms
memory: 26848kb

input:

1000
-757418723 90436380
492915528 -134295398
-874211525 16122778
204169465 -187891707
-242691367 172211001
963766011 -28817654
396669381 -120383389
-705351807 92084168
723125875 -10156233
-490438112 126496051
-966669223 -151601535
-781680399 46058924
-303311696 -276584325
149047354 125216314
580822...

output:

248975

result:

ok single line: '248975'

Test #21:

score: 0
Accepted
time: 290ms
memory: 26896kb

input:

1000
948937975 -400862981
949503258 -402633523
-62248656 -867263748
992412912 23306165
-294026734 -826355663
428366657 -836203727
117442085 945544383
799867257 560855266
-685754722 -565644358
338547350 895435744
-15463705 -871489332
-982752478 -52782254
-368876871 -795873560
405151165 870056639
-961...

output:

249001

result:

ok single line: '249001'

Test #22:

score: 0
Accepted
time: 292ms
memory: 27040kb

input:

1000
-527972426 -670577622
878502001 -387465887
251263072 -781530497
-853954408 -583082000
-769399469 -505745678
-129283302 -417659959
-352808972 -430246191
219886946 -800596228
652814103 -294264025
-421276344 -677366635
651801630 -532370572
352447876 -712646580
-441541536 -684056753
-842728937 -525...

output:

248949

result:

ok single line: '248949'

Test #23:

score: 0
Accepted
time: 245ms
memory: 24636kb

input:

942
-5947 3790
-5041 -1377
-2581 534
-3964 1667
-1151 148
-1008 128
-2076 -192
-4905 384
-3482 1145
-2045 -183
-5410 -2482
-7110 4815
-6510 -3727
-4903 305
-7961 5164
-7375 -4161
-4585 -2662
-5952 -3229
-4927 -651
-3766 1430
-9357 5379
-1273 167
-5832 -3092
-8291 -4384
-4931 881
-5149 -1796
-4674 31...

output:

220416

result:

ok single line: '220416'

Test #24:

score: 0
Accepted
time: 236ms
memory: 24536kb

input:

941
5386 -416
5048 -90
5491 -22
-4627 4490
-2715 5892
-2753 -876
-5388 -5807
-3276 -3399
-2446 -4293
1725 -449
-2394 -4120
5979 90
5100 -83
572 16
-471 -1404
-4664 4515
-2661 4529
-2529 3604
-976 864
-538 528
-2128 2359
-5308 -5767
-3584 3412
-1532 -2405
-2561 3773
-2737 603
-2709 5356
-2969 -2433
-...

output:

198674

result:

ok single line: '198674'

Test #25:

score: 0
Accepted
time: 266ms
memory: 25808kb

input:

974
5256 -701
2279 -59
-2264 946
-2162 6822
-2656 -3628
4290 -579
7985 -573
437 1028
-4411 -6752
12038 -1503
5913 -742
-3330 -5303
-4358 -6704
617 -2537
10163 -949
-3364 -5362
-717 2350
4098 -1078
11309 768
-1642 -5757
6079 -746
-4218 5603
10490 -1012
10328 192
-1610 4192
11825 -1409
4267 -575
5055 ...

output:

216328

result:

ok single line: '216328'

Test #26:

score: 0
Accepted
time: 257ms
memory: 26248kb

input:

987
-5539 1158
9914 -8901
9224 -8535
-12293 2195
1958 3107
3769 5388
1432 -861
3474 -2953
5091 -455
-2411 816
-2316 1349
8300 8074
-9710 802
8428 -8003
4841 8495
201 -144
7660 -7319
-3018 935
9124 8699
7869 -7522
2948 4129
8748 8432
-8146 1072
-10321 651
5162 1652
8988 8606
7005 6706
5318 2698
8536 ...

output:

221600

result:

ok single line: '221600'

Test #27:

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

input:

4
0 -5
5 0
1 1
1 5

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 266ms
memory: 26260kb

input:

983
-3074 -2437
2999 7501
14818 -2250
5472 -3245
3839 -2737
4856 2813
2939 9086
4068 14174
2947 8581
3328 12152
2788 10818
-4950 -2840
1322 -2312
-854 -567
-2057 -1335
7371 -4182
2781 6061
2869 10183
4399 14770
9877 -1207
-735 -472
15290 -2253
-3716 -2540
-3995 -2015
4489 14921
7388 -4193
3114 -2561...

output:

235280

result:

ok single line: '235280'

Test #29:

score: 0
Accepted
time: 278ms
memory: 26764kb

input:

996
500004311 -499999349
499995528 -500004324
160 500004385
-500002749 -500000746
-499998629 -500001288
-500002571 -500001322
1586 500002772
-500002579 -499999901
1632 500001714
-1306 499999484
1957 500002266
-500003862 -500001423
-3413 500003537
-3025 500003357
500001275 -500003374
500001833 -50000...

output:

246973

result:

ok single line: '246973'

Test #30:

score: 0
Accepted
time: 288ms
memory: 26668kb

input:

997
395 500003716
4072 -500004778
499996004 333337794
-500004409 -3591
-3153 499997226
-500000081 1990
-499997209 333335726
1918 500000293
-500001940 741
-500004910 333338117
-787 500004308
-499997413 2767
-500004232 333336772
-499997005 3471
-499997551 333329609
499997259 333333300
-545 -499996641
...

output:

247490

result:

ok single line: '247490'

Test #31:

score: 0
Accepted
time: 272ms
memory: 26296kb

input:

988
-669 -845
1146 -680
635 -2777
5869 3520
371 -4316
-926 3776
2409 3916
-6474 5918
408 -4747
5485 4905
7139 6183
1374 -9960
-4381 4571
-1395 335
429 -6570
489 -6566
5053 3261
1074 -9289
516 -3771
1072 -920
428 -6597
504 -3926
1287 -9787
-7564 7240
972 -1258
-7569 7248
-6105 5603
3981 2759
402 -697...

output:

225908

result:

ok single line: '225908'

Test #32:

score: 0
Accepted
time: 255ms
memory: 25464kb

input:

965
-499999940 -499999730
500000289 313
-3035 2731
499999805 -39
-500000000 500000358
500000258 118
499999559 -470
-76 -343
-500000287 500000365
-500000057 -499999958
-1769 1968
-499999875 499999605
3522 276
-1912 -3061
499999804 499
-500000271 -499999547
499999938 231
-2963 -2829
-499999569 5000003...

output:

203957

result:

ok single line: '203957'

Test #33:

score: 0
Accepted
time: 228ms
memory: 24628kb

input:

939
1482 1260
-500000434 499999806
-1149 1747
-1260 1764
-3404 3034
2618 2273
-553 -392
-90 -3078
2757 2379
-2220 1380
-499999836 499999642
-112 -998
644 1683
-499999699 499999913
499999670 500000167
-1971 1946
499999801 499999965
-3162 2736
2555 2230
-1087 539
-428 -725
-194 -2134
500000495 5000003...

output:

186708

result:

ok single line: '186708'

Test #34:

score: 0
Accepted
time: 247ms
memory: 25188kb

input:

955
-500000461 499999573
-500000200 500000494
499999939 500000463
-39524918 53025080
-99 -500000165
-500000200 500000091
-500000219 499999560
-499999918 499999537
410 -499999818
499999933 500000103
-782940 -97167732
-349 -500000158
7048224 -70490840
500000237 500000298
-121433800 71838974
-31 -50000...

output:

196114

result:

ok single line: '196114'

Test #35:

score: 0
Accepted
time: 252ms
memory: 25868kb

input:

968
-12670145 11374518
49588653 53257314
500000215 500000158
-8908087 -115578630
529677 -71499488
25624561 33337978
-76255449 92204400
499999734 499999840
-120030147 73937760
-500000414 499999624
-46637397 80896480
1095073 -34357320
-65295465 86876630
5074591 -102596268
-500000181 500000227
5792209 ...

output:

197768

result:

ok single line: '197768'

Test #36:

score: 0
Accepted
time: 262ms
memory: 26176kb

input:

977
83649189 40238137
92840791 48787531
155777175 13666781
131614099 -133559403
34560415 9091049
78190421 -55691683
500000145 499999824
499999690 -500000016
213134377 -226679563
8550991 -782899
-17378157 -7445807
149194543 -220979967
-231554525 9693119
126556711 98799479
-43668547 -14871337
-1559746...

output:

209251

result:

ok single line: '209251'

Test #37:

score: 0
Accepted
time: 249ms
memory: 25504kb

input:

962
-121030326 164192864
-195872956 182875129
140748524 -7241051
93616974 -5934996
201849184 -17632706
-500000310 500000030
221383224 -23651916
-203538931 189178264
500000197 53
-159360201 137617484
-178496746 165839629
-128582731 -313281
-499999956 500000192
499999784 110
-155271681 -137562626
-225...

output:

201519

result:

ok single line: '201519'

Test #38:

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

input:

4
0 1
1000000000 -1000000000
1 0
-1000000000 1000000000

output:

1

result:

ok single line: '1'

Test #39:

score: 0
Accepted
time: 226ms
memory: 24036kb

input:

928
170269973 -272038995
136492629 156219873
-47171679 -19145691
305743329 -317318107
141297165 165392169
99585057 -96527839
175220101 -36616731
156001957 -202737203
-272548095 -3130571
-11356047 -27298843
148722357 -180534423
104753573 108101717
297954157 -313023143
-14559071 -26352495
171725893 27...

output:

194714

result:

ok single line: '194714'

Test #40:

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

input:

6
0 0
-2 -99
-100 -100
-56 -55
-100 0
0 -100

output:

4

result:

ok single line: '4'

Test #41:

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

input:

6
-100 0
2021 2023
-2022 0
2019 -2021
99 101
99 -99

output:

1

result:

ok single line: '1'

Test #42:

score: 0
Accepted
time: 284ms
memory: 26972kb

input:

1000
-742147404 -283695660
-466639637 288446353
-83175126 146887879
969866611 -661949195
334569680 -966256649
55429457 51833284
-748377689 -415645264
34617026 853758184
-118667814 392964857
-929275128 -49421111
-19389314 614045676
-12269024 -39409010
901905217 -20981356
-81827036 -37385291
584210585...

output:

248992

result:

ok single line: '248992'

Test #43:

score: 0
Accepted
time: 157ms
memory: 19340kb

input:

774
-26422194 60886359
452287984 458733035
-6427410 -261937333
-265362764 587539606
671091287 -196803029
-406574773 -714708522
-370481503 -448336592
-633039773 764194633
562006117 355891150
-247317078 58953343
-342293532 -775239898
-688832160 -409147438
515472348 7385278
727654419 164961897
-8472053...

output:

148996

result:

ok single line: '148996'

Test #44:

score: 0
Accepted
time: 290ms
memory: 26780kb

input:

1000
-72285764 -581996567
-822447341 -398199852
-331102816 -910495620
-235765662 -51188181
-654757419 -15344880
-73989701 -106766327
-561359665 -236163519
-462377613 -952098496
-888525203 -359979765
-626973746 -922268418
-766692243 -653113679
-946363316 -357536066
-483253705 -857013734
-364199596 -5...

output:

248909

result:

ok single line: '248909'