QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#372926 | #3663. The Biggest Triangle | _SIGMA# | WA | 14ms | 3940kb | C++14 | 2.7kb | 2024-03-31 20:59:44 | 2024-03-31 20:59:45 |
Judging History
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