QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#940862#393. Signalingltunjic#0 341ms3968kbC++202.7kb2025-03-18 03:41:452025-03-18 03:41:50

Judging History

This is the latest submission verdict.

  • [2025-03-18 03:41:50]
  • Judged
  • Verdict: 0
  • Time: 341ms
  • Memory: 3968kb
  • [2025-03-18 03:41:45]
  • Submitted

answer

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <chrono>
#include <random>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;

const int N = 1510;
const int RND = 1e6;
const ld OFF = 1e-8;

struct point { 
	ld x, y;
	point() {}
	point(int x, int y) : x(x), y(y) {}
	void rotate() { 
		ld z = y;
		y = -x;
		x = z;
	}

	void print() { 
		printf("%.3LF %.3LF\n", x, y);
	}
};

int n;
point P[N];

point ortho(point a, point b) { 
	if(a.y == b.y) { return point(0, 0); }
	if(a.x > b.x) { swap(a, b); }
	point c = point(b.x - a.x, b.y - a.y);
	c.rotate();
	point d = point((a.x + b.x) / 2, (a.y + b.y) / 2);
	c.x += d.x;
	c.y += d.y;
	return point((c.y - d.y) / (c.x - d.x), c.y - (c.y - d.y) / (c.x - d.x) * c.x);
}

point inter(point a, point b) { 
	point c;
	c.x = (b.y - a.y) / (a.x - b.x);
	c.y = a.x * c.x + a.y;
	return c;
}

ld dist(point a, point b) { 
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

ld abs_(ld x) { return x < 0 ? -x : x; }

int triple(int a, int b, int c) { 
	point l1 = ortho(P[a], P[b]);
	point l2 = ortho(P[a], P[c]);
	if(P[a].y == P[b].y) { l1 = ortho(P[b], P[c]); }
	if(P[a].y == P[c].y) { l2 = ortho(P[b], P[c]); }

	point s = inter(l1, l2);

//	l1.print();
//	l2.print();
//	s.print();

	ld d = dist(s, P[a]);
//	printf("d %.3LF, %.3LF %.3LF %.3LF\n", d, dist(s, P[a]), dist(s, P[b]), dist(s, P[c]));
	int ret = 0;
	for(int i = 0; i < n; ++i) { 
		if(dist(P[i], s) < d || abs_(dist(P[i], s) - d) < OFF) { ++ret; }
	}
//	printf("%d\n", ret);
	return ret;
}

int main() { 
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) { 
		int x, y;
		scanf("%d%d", &x, &y);
		P[i] = point(x, y);
	}

	if(n < 100) { 
		int cnt = 0;
		for(int i = 0; i < n; ++i)
			for(int j = i + 1; j < n; ++j)
				for(int k = j + 1; k < n; ++k) { 
					cnt += triple(i, j, k);
//					printf("%d %d %d %d\n", i, j, k, triple(i, j, k));
				}
		printf("%.3LF\n", (ld) cnt / ((n * (n - 1) * (n - 2)) / 6));
		return 0;
	}

	ll cnt = 0;
	for(int i = 0; i < RND; ++i) { 
		int x = rng() % n;
		int y = rng() % n;
		int z = rng() % n;
		if(x == y || x == z || y == z) { 
			--i;
			continue;
		}

//		int x = rng() % n;
//		int y = rng() % (n - 1);
//		int z = rng() % (n - 2);
//		y += y >= x;
//		if(y > x) { swap(y, x); }
//		z += (z >= y);
//		z += (z >= x);


//		printf("x: "); P[x].print();
//		printf("y: "); P[y].print();
//		printf("z: "); P[z].print();
//		printf("%d %d %d ", x, y, z);
		cnt += triple(x, y, z);
	}
	printf("%.3LF\n", (ld) cnt / RND);
	return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3840kb

input:

10
-50 46
12 -45
-75 -9
63 -90
-55 58
34 -93
12 -56
-39 -92
-94 2
-97 56

output:

2.992

result:

wrong answer 1st numbers differ - expected: '5.91667', found: '2.99200', error = '0.49431'

Test #2:

score: 0
Wrong Answer
time: 7ms
memory: 3968kb

input:

20
-92 -19
54 50
-73 8
31 99
-87 77
100 -23
27 71
70 47
-66 -61
-95 51
-69 -35
-72 22
-77 -54
-68 53
50 -32
-43 -42
3 59
-95 3
-7 -2
-43 -64

output:

6.836

result:

wrong answer 1st numbers differ - expected: '10.38333', found: '6.83600', error = '0.34164'

Test #3:

score: 0
Wrong Answer
time: 341ms
memory: 3840kb

input:

50
-453 9273
8635 5374
7799 -7270
4790 5371
-4527 7088
-5703 116
1861 413
4233 -8269
-806 -6547
2147 -6368
6555 -7298
56 -2857
2201 7138
938 7735
-5991 3010
-2957 382
-8048 2456
449 -9863
-9972 8117
558 7923
-9198 -9065
-8252 5549
-7689 939
-3073 -9730
5708 -8504
-3763 -9209
7681 2139
5616 -4776
280...

output:

15.471

result:

wrong answer 1st numbers differ - expected: '23.31775', found: '15.47100', error = '0.33651'

Test #4:

score: 0
Time Limit Exceeded

input:

100
-2141 -4880
-9922 -5732
-1447 6911
-1075 -6956
-6494 -3573
8708 6799
4213 2423
6020 -1331
8680 4477
-8039 -2826
-7634 -528
-2889 -9898
4520 -6714
-2444 -4444
1162 1172
-2956 -6434
-8580 4504
-4828 837
7455 6831
-3319 2977
6809 -6073
7342 4840
6805 -1347
6238 6681
-1140 7819
6874 3130
-1002 -9025...

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

200
-1122 14370
-42358 19597
-8142 -62821
-96727 50998
-39983 -1255
-9889 -32277
-76715 -26038
56558 30000
40878 -16623
-48090 -48731
15995 -5641
75446 -54677
63957 10714
-73685 58774
-51402 -9966
43245 13215
64833 62221
-33150 -97182
-57948 -30006
-39542 -59193
75510 70480
54803 6772
-20806 -42135
...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

450
311476 420680
-179437 -453868
692958 -289805
882929 -536362
-635778 -76866
-452292 737474
-319376 -97126
-436325 -624165
-830541 -235691
-32100 -25859
269774 -319553
-952967 -665867
-759030 -379696
-799622 531046
162770 929102
959448 -820442
-696548 250017
315619 869226
-950422 483601
-238243 92...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

500
901932 -831127
177611 -452336
-81615 -260260
-868737 915377
-805269 -567574
-621357 -983383
-478831 -753449
-146546 929599
-705635 256170
55217 -697919
-708568 -316283
720771 -686336
568982 851708
569161 638609
-641368 -750581
-247391 301211
-342708 673355
393219 -184972
-676469 154890
-559945 8...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000
618441 536922
-670652 756937
-951203 -88976
-96750 102377
-49403 267613
-202790 492478
328782 -572207
-401320 -225835
-533681 -451907
298806 -554354
-933347 -292249
-396171 -911579
-211258 458880
60941 -128449
-856581 -816717
-782661 221946
219834 -400346
531242 -745577
-789282 -735078
253598 5...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

1500
-466267 -545644
842097 -947922
699094 -376679
708277 42478
712256 813305
-629139 377724
795013 -265652
885435 362587
105505 -151452
419402 618775
-824399 431939
936446 382165
-227899 -244470
476667 778569
-349480 729226
-248801 -328251
-829799 -147620
270009 -822539
-760492 814759
-278341 -5627...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

1500
372361 -892254
674948 369064
663890 427706
-962493 -748469
-296124 -837649
366715 89587
414772 -877335
-788861 594332
-306600 -691
-443204 -140585
325874 -187797
-549930 -649347
-689284 -598867
-174278 921052
-691067 551110
-491282 -305052
439793 -153742
858640 165072
141049 845958
-974583 3462...

output:


result: