QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375095#3663. The Biggest TriangleChineseElNayemWA 6ms3944kbC++232.0kb2024-04-02 21:28:412024-04-02 21:28:46

Judging History

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

  • [2024-04-02 21:28:46]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3944kb
  • [2024-04-02 21:28:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct line{
    double x1,y1;
    double m=1e18,c;
    bool isVer = 0;
};
struct point{
    double x,y;
};
point calc(line a, line b)
{
    point ret;
    if(a.isVer)
    {
        ret.x = a.x1;
        ret.y = a.x1 * b.m + b.c;
    }
    else if(b.isVer)
    {
        ret.x = b.x1;
        ret.y = b.x1 * a.m + a.c;
    }
    else
    {
        ret.x = (b.c - a.c) / (a.m - b.m);
        ret.y = a.m * ret.x + a.c;
    }
    return ret;
}
double dist(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    line lines[n];

    for(int i = 0; i < n; i++)
    {
        double x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        lines[i].x1 = x1;
        lines[i].y1 = y1;

        if(x1 == x2)
        {
            lines[i].isVer = 1;
            lines[i].m = 1e18;
            continue;
        }

        lines[i].m = (y2 - y1) / (x2 - x1);
        lines[i].c = -lines[i].m * x1 + y1;
    }

    double ans = 0;

    for(int a = 0; a < n; a++)
    {
        for(int b = a + 1; b < n; b++)
        {
            for(int c = b + 1; c < n; c++)
            {
                
                set<int> s;
                s.insert(lines[a].m);
                s.insert(lines[b].m);
                s.insert(lines[c].m);
                if(s.size() != 3)
                    continue;

                point ab = calc(lines[a], lines[b]);
                point bc = calc(lines[b], lines[c]);
                point ca = calc(lines[a], lines[c]);

                double tdist = dist(ab, bc) + dist(bc, ca) + dist(ca, ab);

                ans = max(ans, tdist);

            }
        }
    }

    if(ans)
        cout << fixed << setprecision(10) << ans << '\n';
    else
        cout << "no triangle\n";

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3844kb

input:

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

output:

3.4142135624

result:

ok 

Test #2:

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

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

input:

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

output:

12.0000000000

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 3708kb

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

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:

510775.0347072277

result:

wrong answer