QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87654#3663. The Biggest TriangleZuqa#WA 2ms3724kbC++203.3kb2023-03-13 23:13:412023-03-13 23:13:45

Judging History

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

  • [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:13:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3724kb
  • [2023-03-13 23:13:41]
  • 提交

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-8, 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;

    double determinant = a1 * b2 - a2 * b1;
    if(determinant == 0)
    {
        // Same line aka Rakbin fo2 b3d
        if(isCollinear(A, B, C) && isCollinear(A, B, D))
            return pt(INF, INF);

        // The lines are parallel.
        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(A.x == INF && A.y == INF)
        return false;
    if(A.x == -INF && A.y == -INF)
        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; j < n; j++)
            {
                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) || isCollinear(A, B, C))
                    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: 0ms
memory: 3632kb

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: 0ms
memory: 3452kb

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: 3660kb

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: 0ms
memory: 3444kb

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: -100
Wrong Answer
time: 2ms
memory: 3724kb

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:

12283563.651809119197

result:

wrong answer