QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#940862 | #393. Signaling | ltunjic# | 0 | 341ms | 3968kb | C++20 | 2.7kb | 2025-03-18 03:41:45 | 2025-03-18 03:41:50 |
Judging History
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...