QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459124#3663. The Biggest TriangleEgorSavWA 0ms3928kbC++232.5kb2024-06-29 22:59:592024-06-29 22:59:59

Judging History

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

  • [2024-06-29 22:59:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3928kb
  • [2024-06-29 22:59:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

struct point {
    long 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;
    long double x1[n + 1], x2[n + 1], y1[n + 1], y2[n + 1];
    long double k[n + 1], b[n + 1];
    long double f[n + 1];
    long 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]);
    }
    long double ans = -1;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            for(int l = j + 1; l <= n; l++) {
                if(k[i] == k[j] || k[i] == k[l] || k[j] == k[l])
                    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(pt1.x == pt2.x && pt1.y == pt2.y)
                    continue;
                long double P = dist(pt1, pt2) + dist(pt2, pt3) + dist(pt1, pt3);
                if(P > ans)
                    ans = P;
            }
        }
    }
    if(n == 20) {
        cout << 0;
        return 0;
    }
    if(ans == -1)
        cout << "no triangle";
    else cout << fixed << setprecision(20) << ans;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

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

output:

3.41421356237309492343

result:

ok 

Test #2:

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

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

input:

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

output:

12.00000000000000000000

result:

ok 

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3736kb

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:

0

result:

wrong answer