QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#459292 | #3663. The Biggest Triangle | EgorSav | WA | 2ms | 3980kb | C++23 | 2.5kb | 2024-06-30 00:58:27 | 2024-06-30 00:58:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct point {
double x, y;
};
double dist(point t1, point t2) {
return sqrt((t1.x - t2.x) * (t1.x - t2.x) + (t1.y - t2.y) * (t1.y - t2.y));
}
int main() {
int n;
cin >> n;
double x1[n + 1], x2[n + 1], y1[n + 1], y2[n + 1];
double k[n + 1], b[n + 1];
double f[n + 1];
double inf = 1e5;
fill(f, f + 1 + n, inf);
for(int i = 1; i <= n; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
if(x1[i] == x2[i]) {
f[i] = x1[i];
k[i] = inf;
continue;
}
k[i] = (y2[i] - y1[i]) / (x2[i] - x1[i]);
b[i] = (y1[i] - k[i] * x1[i]);
}
double ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
for(int l = j + 1; l <= n; l++) {
if(abs(k[i] - k[j]) <= 0.00001 || abs(k[i] - k[l]) <= 0.00001 || abs(k[j] - k[l]) <= 0.00001)
continue;
point pt1, pt2, pt3;
if(k[i] == inf)
pt1.x = f[i];
else if(k[j] == inf)
pt1.x = f[j];
else
pt1.x = (b[j] - b[i]) / (k[i] - k[j]);
if(k[i] != inf)
pt1.y = k[i] * pt1.x + b[i];
else pt1.y = k[j] * pt1.x + b[j];
if(k[i] == inf)
pt2.x = f[i];
else if(k[l] == inf)
pt2.x = f[l];
else
pt2.x = (b[l] - b[i]) / (k[i] - k[l]);
if(k[i] != inf)
pt2.y = k[i] * pt2.x + b[i];
else pt2.y = k[l] * pt2.x + b[l];
if(k[j] == inf)
pt3.x = f[j];
else if(k[l] == inf)
pt3.x = f[l];
else
pt3.x = (b[j] - b[l]) / (k[l] - k[j]);
if(k[j] != inf)
pt3.y = k[j] * pt3.x + b[j];
else pt3.y = k[l] * pt3.x + b[l];
if(abs(pt1.x - pt2.x) <= 0.00001 && abs(pt1.y - pt2.y) <= 0.00001)
continue;
double P = dist(pt1, pt2) + dist(pt2, pt3) + dist(pt1, pt3);
if(P > ans)
ans = P;
}
}
}
if(ans == 0)
cout << "no triangle";
else cout << fixed << setprecision(6) << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3972kb
input:
3 0 0 0 1 0 0 1 0 0 1 1 0
output:
3.414214
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 0 0 0 1 0 0 1 0 0 0 1 1
output:
no triangle
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 0 0 0 1 0 4 3 0 0 0 1 0 -1 -1 1 1
output:
12.000000
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
20 0 0 10 1 0 0 18 1 0 0 16 1 0 0 14 1 0 0 0 1 0 0 17 1 0 0 11 1 0 0 2 1 0 0 3 1 0 0 9 1 0 0 5 1 0 0 7 1 0 0 4 1 0 0 19 1 0 0 6 1 0 0 15 1 0 0 8 1 0 0 1 1 0 0 13 1 0 0 12 1
output:
no triangle
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
100 -1086 -690 -818 616 2109 2485 -455 -560 31 -680 -260 -804 -427 2531 88 418 -852 -982 -57 14 -361 -5831 121 -1255 443 79 974 -592 -1946 1682 -1884 589 -941 69 -910 -611 74 -292 -616 714 3574 3254 908 562 -4123 -301 961 167 -245 -836 -571 781 844 62 -320 304 789 -295 -88 -637 1199 1365 -616 -1508 ...
output:
12352116.277207
result:
ok
Test #6:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
100 -944 5551 -400 1443 504 -1168 1536 -466 1475 668 -404 -570 -390 -63 -1717 101 923 4554 -466 -1679 2307 566 1115 525 193 -48 -274 699 -3079 -3465 588 1087 -252 -1408 -1153 -24 4471 -1055 988 -373 48 248 -469 -1307 3143 2560 829 927 1079 -170 36 396 -1156 -2459 471 245 353 2927 752 1406 -3767 1685...
output:
2553320.293467
result:
ok
Test #7:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
100 -962 186 663 -478 -860 -786 852 -406 -1648 634 1159 -805 3699 5438 631 947 -685 -698 -990 194 7466 -3888 1558 -983 -1001 -3536 523 1280 2967 -381 -1373 -177 -1974 -1207 -748 -626 1537 -534 -530 416 2268 3597 -794 -1538 885 814 -656 -948 2231 2096 -517 -525 437 -1599 926 -1428 5689 -1284 -1365 24...
output:
6418642.331338
result:
ok
Test #8:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
100 7722 -3104 -9865 -5532 7394 6046 113 2456 7823 7603 -7836 -7435 9819 6146 -9499 -3317 3741 1796 226 -7257 -9239 -2165 -9087 9264 6798 2042 -4975 5261 -1533 -6390 9448 4652 -876 -2807 2540 2584 6607 1133 -2519 9340 -1354 -7085 -8558 -4928 339 9142 8466 5893 -7926 7279 5710 4244 467 2633 -9205 -61...
output:
57991431.166345
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 3916kb
input:
100 -7986 1112 -5473 358 -1009 5926 5769 9954 832 -1167 -7448 5029 -4771 -6472 6791 -1515 8314 3256 9923 4673 3804 -4789 9905 3734 -5859 -6317 9153 -6349 -3905 5803 -360 -6723 3951 -1408 -952 -6375 1655 6681 7564 -7552 -9736 -8660 9917 -9515 -5462 -5974 3372 2617 5772 -9114 265 -5399 -7213 2846 8979...
output:
1030246220.309010
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
100 -5876 7730 8652 -5022 -8861 7 4538 6916 8856 3626 -3115 5358 -3334 2826 -7126 -6803 7540 3176 -6016 6604 5288 -4498 -8943 -3397 -2365 -2113 -6883 9611 2385 3319 -7718 7955 -3033 7224 -3489 -2841 6114 -7023 -3727 -6736 6816 -5733 9785 -3601 8030 8901 7032 4143 9685 2940 -1412 5444 9754 -9054 1494...
output:
60810745.885452
result:
ok
Test #11:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
100 5302 4446 2050 -9610 -3532 8582 -3315 -7768 6067 -5691 -7125 7006 8151 3269 -860 -3189 -7421 4027 -9253 7843 5636 1230 -9906 -3523 -329 3725 4708 6837 -709 -7897 -8726 -7180 1342 2416 3517 2483 -2392 -721 5882 3124 8146 -9979 4251 -546 5896 -4954 3077 4140 2939 9208 9682 -105 5390 7945 2113 -37 ...
output:
34329826.391249
result:
ok
Test #12:
score: 0
Accepted
time: 2ms
memory: 3980kb
input:
100 5429 -7445 8797 7155 -8344 -5436 5284 8452 -5564 8453 -1537 -7348 -89 1689 -5722 5332 2144 -8599 808 -6617 -6701 -6394 41 103 9009 1969 -4086 -9768 5566 3269 3257 -2990 -7008 3689 -1258 5935 4153 6148 2346 -5235 4064 -3261 3896 -3707 -1231 -7651 -5516 5236 546 1890 -453 4741 1258 -1938 -4683 511...
output:
105643194.563484
result:
ok
Test #13:
score: 0
Accepted
time: 2ms
memory: 3972kb
input:
100 -516 512 6556 -4112 22 -1138 2482 -150 -180 -839 -1467 -1142 -621 -559 6871 -899 120 -796 2384 -492 -762 -703 -2776 -762 -262 -631 -956 -1249 -1152 1225 -5960 4963 -1261 187 1252 -644 -1411 -710 -4074 -776 -233 1135 -1737 -7165 208 563 -2243 -3946 476 -225 -1076 613 1393 57 -6615 -3931 -476 -441...
output:
6543389.988937
result:
ok
Test #14:
score: -100
Wrong Answer
time: 2ms
memory: 3980kb
input:
100 521 -356 3537 -2756 1015 790 -987 844 405 -1097 -1793 993 1134 -361 4790 -979 -866 -317 -350 478 67 -1313 -2041 3001 855 -1197 -6513 6967 1171 -65 -3145 1753 333 -355 -987 844 554 -128 2095 -1100 446 -144 -694 -52 -243 1131 208 2314 -362 198 -30 448 928 169 -3938 -494 -500 -1401 -1082 2646 533 -...
output:
2294089.133229
result:
wrong answer