QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372926#3663. The Biggest Triangle_SIGMA#WA 14ms3940kbC++142.7kb2024-03-31 20:59:442024-03-31 20:59:45

Judging History

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

  • [2024-03-31 20:59:45]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:3940kb
  • [2024-03-31 20:59:44]
  • 提交

answer

#include<bits/stdc++.h>
#include<unordered_map> 
#define print(v,T) copy(v.begin(), v.end(), ostream_iterator<T>(cout, " "));
#define TATAKAAI ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define el "\n"
#define ell cout<<"\n"
#define forn(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define forb(i, n) for (int i = n-1; i >= 0; i--)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;

const ll N = 1000000007;
int dy[] = { 1,-1,0,0,1,-1 };
int dx[] = { 0,0,-1,1,1,-1 };

int main() {
    TATAKAAI;
    int n;
    cin >> n;

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

    double ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                double mi = (x2[i] == x1[i] ? 1e9 : (y2[i] - y1[i]) / (x2[i] - x1[i]));
                double mj = (x2[j] == x1[j] ? 1e9 : (y2[j] - y1[j]) / (x2[j] - x1[j]));
                double mk = (x2[k] == x1[k] ? 1e9 : (y2[k] - y1[k]) / (x2[k] - x1[k]));

                if (mi == mj || mj == mk || mi == mk)
                    continue;

                double c1 = y1[i] - mi * x1[i];
                double c2 = y1[j] - mj * x1[j];
                double c3 = y1[k] - mk * x1[k];

                double x12 = (c2 - c1) / (mi - mj);
                double x23 = (c3 - c2) / (mj - mk);
                double x13 = (c3 - c1) / (mi - mk);

                //1  -> 2
                if (mi == 1e9)
                {
                    x12 = x1[i];
                    x13 = x1[i];
                }
                if (mj == 1e9)
                {
                    x23 = x1[j];
                    x12 = x1[j];
                }
                if (mk == 1e9)
                {
                    x13 = x1[k];
                    x23 = x1[k];
                }

                double y12 = (mi == 1e9 ? mj * x12 + c2 : mi * x12 + c1);
                double y23 = (mj == 1e9 ? mk * x23 + c3 : mj * x23 + c2);
                double y13 = (mk == 1e9 ? mi * x13 + c1 : mk * x13 + c3);


                double d1 = sqrt(((x12 - x23) * (x12 - x23)) + ((y12 - y23) * (y12 - y23)));
                double d2 = sqrt(((x23 - x13) * (x23 - x12)) + ((y23 - y13) * (y23 - y13)));
                double d3 = sqrt(((x12 - x13) * (x12 - x13)) + ((y12 - y13) * (y12 - y13)));

                ans = max(ans, d1 + d2 + d3);
            }
        }
    }

    if (ans == 0)
        cout << "no triangle";
    else
        cout << fixed << setprecision(10) << ans;

    return 0;
}

详细

Test #1:

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

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: 1ms
memory: 3748kb

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: 1ms
memory: 3940kb

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

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: 14ms
memory: 3864kb

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:

3901.8275889436

result:

wrong answer