QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#451188 | #3663. The Biggest Triangle | zedanov | RE | 0ms | 0kb | C++20 | 2.1kb | 2024-06-22 22:25:22 | 2024-06-22 22:25:22 |
answer
#include <bits/stdc++.h>
using namespace std;
#define zedanov \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define ld long double
#define el "\n"
const int N = 1e5 + 5, md = 1e9 + 7;
ld inf = LDBL_MAX;
// Verify Logic, Check Constrains
// Overflow, Fits in Time/Memory ?
struct point
{
ld x, y;
double dist(const point &other)
{
abs(sqrtl((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y)));
}
};
struct line
{
ld m, c;
point intersect(const line &other)
{
ld x, y;
if (m == other.m)
return {inf, inf};
x = (other.c - c) / (m - other.m);
y = m * x + c;
return {x, y};
}
};
void doWork()
{
int n;
cin >> n;
vector<line> a(n);
for (int i = 0; i < n; i++)
{
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2)
{
a[i].m = inf;
a[i].c = x1;
}
else if (y1 == y2)
{
a[i].m = 0;
a[i].c = y1;
}
else
{
a[i].m = (y2 - y1) / (x2 - x1);
a[i].c = y1 - a[i].m * x1;
}
}
double ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
for (int k = 0; k < n; k++)
{
if (i == k || j == k)
continue;
auto p1 = a[i].intersect(a[j]);
auto p2 = a[i].intersect(a[k]);
auto p3 = a[j].intersect(a[k]);
if (p1.x == inf || p2.x == inf || p3.x == inf)
continue;
ans = max(ans, p1.dist(p2) + p1.dist(p3) + p2.dist(p3));
}
}
}
if (ans > 0)
cout << fixed << setprecision(8) << ans;
else
cout << "no triangle";
}
signed main()
{
zedanov int t = 1;
// cin >> t;
while (t--)
doWork();
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
3 0 0 0 1 0 0 1 0 0 1 1 0