QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#459124 | #3663. The Biggest Triangle | EgorSav | WA | 0ms | 3928kb | C++23 | 2.5kb | 2024-06-29 22:59:59 | 2024-06-29 22:59:59 |
Judging History
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