QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87656#3663. The Biggest TriangleZuqa#AC ✓6ms3752kbC++203.1kb2023-03-13 23:20:322023-03-13 23:20:33

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-13 23:20:33]
  • Judged
  • Verdict: AC
  • Time: 6ms
  • Memory: 3752kb
  • [2023-03-13 23:20:32]
  • Submitted

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

#define x real()
#define y imag()

const int INF = 1e9;
const ld eps = 1e-10, pi = acos(-1);

int dcmp(ld a, ld b)
{
    // a == b : 0
    // a != b : != 0
    // a > b : 1
    // a < b : -1
    // a >= b : != -1
    // a <= b : != 1
    return fabs(a - b) <= eps ? 0 : a < b ? -1 : 1;
}

ld cross(pt a, pt b)
{
    return ((conj(a) * (b)).imag());
}

bool isCollinear(pt a, pt b, pt c)
{
    return dcmp(cross(b - a, c - a), 0) == 0;
}

pt lineLineIntersection(pt A, pt B, pt C, pt D)
{
    // Line AB represented as a1x + b1y = c1
    ld a1 = B.y - A.y;
    ld b1 = A.x - B.x;
    ld c1 = A.x * B.y - B.x * A.y;
    // Line CD represented as a2x + b2y = c2
    ld a2 = D.y - C.y;
    ld b2 = C.x - D.x;
    ld c2 = C.x * D.y - D.x * C.y;

    ld determinant = a1 * b2 - a2 * b1;
    if(dcmp(determinant, 0) == 0)
        return pt(INF, INF);
    else
    {
        ld X = (b2 * c1 - b1 * c2) / determinant;
        ld Y = (a1 * c2 - a2 * c1) / determinant;
        return pt(X, Y);
    }
}

ld solve(pt a, pt b, pt c)
{
    return abs(a - b) + abs(a - c) + abs(b - c);
}

bool check(pt A)
{
    if(dcmp(A.x, INF) == 0)
        return false;
    return true;
}

void doWork()
{
    int n;
    cin >> n;
    vector<pair<pt, pt>> v;
    for(int i = 0, x1, y1, x2, y2; i < n; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        v.push_back({pt(x1, y1), pt(x2, y2)});
    }
    ld ans = -100;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            pt A = lineLineIntersection(v[i].first, v[i].second, v[j].first, v[j].second);
            if(!check(A))
                continue;
            for(int k = j + 1; k < n; k++)
            {
                pt B = lineLineIntersection(v[i].first, v[i].second, v[k].first, v[k].second);
                pt C = lineLineIntersection(v[j].first, v[j].second, v[k].first, v[k].second);

                if(!check(B) || !check(C))
                    continue;
                if(dcmp(solve(A, B, C), 0) == 0)
                    continue;
                ans = max(ans, solve(A, B, C));
            }
        }
    }
    if(ans < 0)
        cout << "no triangle";
    else
        cout << fixed << setprecision(12) << ans;
}

signed main()
{
    FIO
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3720kb

input:

3
0 0 0 1
0 0 1 0
0 1 1 0

output:

3.414213562373

result:

ok 

Test #2:

score: 0
Accepted
time: 2ms
memory: 3372kb

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: 2ms
memory: 3616kb

input:

4
0 0 0 1
0 4 3 0
0 0 1 0
-1 -1 1 1

output:

12.000000000000

result:

ok 

Test #4:

score: 0
Accepted
time: 2ms
memory: 3460kb

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: 6ms
memory: 3656kb

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.277207863721

result:

ok 

Test #6:

score: 0
Accepted
time: 3ms
memory: 3624kb

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.293466765695

result:

ok 

Test #7:

score: 0
Accepted
time: 3ms
memory: 3684kb

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.331337538568

result:

ok 

Test #8:

score: 0
Accepted
time: 6ms
memory: 3752kb

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.166361718293

result:

ok 

Test #9:

score: 0
Accepted
time: 3ms
memory: 3716kb

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.307099049794

result:

ok 

Test #10:

score: 0
Accepted
time: 6ms
memory: 3672kb

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.885459589237

result:

ok 

Test #11:

score: 0
Accepted
time: 3ms
memory: 3664kb

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.391249432174

result:

ok 

Test #12:

score: 0
Accepted
time: 3ms
memory: 3752kb

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.563467648739

result:

ok 

Test #13:

score: 0
Accepted
time: 6ms
memory: 3660kb

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.988937080533

result:

ok 

Test #14:

score: 0
Accepted
time: 6ms
memory: 3660kb

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:

211316352.815967714472

result:

ok 

Test #15:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

3
0 1 1 -1
0 -1 1 1
0 3 1 -3

output:

no triangle

result:

ok 

Test #16:

score: 0
Accepted
time: 4ms
memory: 3684kb

input:

100
305 1242 -2963 702
286 469 -1310 1745
-766 -708 -1174 -399
-832 364 -1472 -1122
623 124 -3301 -4440
-1328 308 -3268 2958
88 -124 534 769
262 1136 1036 1165
1234 -1054 -1950 -980
384 1217 -2304 887
53 -334 -769 -1700
-347 -1389 -512 1107
439 846 -512 1107
-257 1258 -1277 654
-235 56 -481 -2090
75...

output:

7359005.217675995726

result:

ok 

Test #17:

score: 0
Accepted
time: 6ms
memory: 3668kb

input:

100
490 -1236 -1193 5733
-613 722 4335 3362
-815 -563 2063 3327
1070 220 3352 -1514
-766 457 4794 4157
1187 -1224 3703 -5846
1130 -997 -3674 7339
-663 367 -71 1087
-1366 1004 3814 1336
-1100 -511 -3158 -3707
335 327 624 1382
-655 -135 1681 4753
-322 1297 682 457
1323 868 2022 354
-156 1287 -1716 109...

output:

4311750.931301936649

result:

ok 

Test #18:

score: 0
Accepted
time: 2ms
memory: 3368kb

input:

20
0 13 1 13
0 11 1 11
0 16 1 16
0 0 1 0
0 17 1 17
0 4 1 4
0 14 1 14
0 7 1 7
0 18 1 18
0 19 1 19
0 12 1 12
0 6 1 6
0 5 1 5
0 1 1 1
0 8 1 8
0 15 1 15
0 10 1 10
0 2 1 2
0 3 1 3
0 9 1 9

output:

no triangle

result:

ok 

Test #19:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

20
18 0 18 1
19 0 19 1
17 0 17 1
7 0 7 1
4 0 4 1
16 0 16 1
6 0 6 1
8 0 8 1
9 0 9 1
14 0 14 1
1 0 1 1
13 0 13 1
5 0 5 1
11 0 11 1
3 0 3 1
10 0 10 1
15 0 15 1
0 0 0 1
12 0 12 1
2 0 2 1

output:

no triangle

result:

ok 

Test #20:

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

input:

40
0 0 1 0
4 0 4 1
0 15 1 15
0 6 1 6
0 18 1 18
0 10 1 10
12 0 12 1
0 11 1 11
17 0 17 1
0 17 1 17
2 0 2 1
8 0 8 1
0 13 1 13
7 0 7 1
0 0 0 1
15 0 15 1
0 4 1 4
14 0 14 1
11 0 11 1
6 0 6 1
0 12 1 12
0 5 1 5
9 0 9 1
0 16 1 16
0 8 1 8
0 19 1 19
3 0 3 1
0 2 1 2
10 0 10 1
16 0 16 1
1 0 1 1
0 1 1 1
19 0 19 1...

output:

no triangle

result:

ok 

Test #21:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

20
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -10000 9995 9983
-10000 -1...

output:

no triangle

result:

ok 

Test #22:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

20
-10000 -10000 9991 9979
-10000 -10000 9987 9975
-10000 -10000 9983 9971
-10000 -10000 9988 9976
-10000 -10000 9994 9982
-10000 -10000 9989 9977
-10000 -10000 9992 9980
-10000 -10000 9984 9972
-10000 -10000 9977 9965
-10000 -10000 9980 9968
-10000 -10000 9978 9966
-10000 -10000 9976 9964
-10000 -1...

output:

no triangle

result:

ok 

Test #23:

score: 0
Accepted
time: 3ms
memory: 3684kb

input:

100
-103 -1625 -450 -1632
610 1988 363 16
165 -681 360 1785
-98 942 -235 -142
300 -614 241 700
222 887 -95 363
1075 3666 -270 -1180
240 -956 -602 968
2746 1901 -746 -231
-1399 -3994 541 1735
716 847 881 166
-711 866 333 -924
-642 -973 -35 395
-505 -96 -94 214
393 -849 -946 -746
-942 509 -1549 -859
4...

output:

2516645.867689868699

result:

ok 

Test #24:

score: 0
Accepted
time: 6ms
memory: 3668kb

input:

100
-42 639 684 679
4015 -1043 -901 250
-601 -215 604 590
4730 2714 1127 643
932 1353 518 884
294 -846 958 -909
258 294 912 -309
165 -411 -269 -4
-2667 245 -495 1
-1447 -1809 -124 -1558
-869 2139 272 -625
-1232 3960 -260 930
-481 -2758 -291 -561
-1160 1188 -305 847
-664 -666 -439 -603
461 273 -394 6...

output:

75090836.238786895417

result:

ok