QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459292#3663. The Biggest TriangleEgorSavWA 2ms3980kbC++232.5kb2024-06-30 00:58:272024-06-30 00:58:27

Judging History

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

  • [2024-06-30 00:58:27]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3980kb
  • [2024-06-30 00:58:27]
  • 提交

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;
}

详细

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