QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#451153 | #3663. The Biggest Triangle | zedanov | WA | 0ms | 3732kb | C++17 | 3.3kb | 2024-06-22 21:38:27 | 2024-06-22 21:38:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define zedanov \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define int long long
#define el "\n"
const int N = 1e5 + 5, md = 1e9 + 7, inf = 1e9;
double EPS = 1e-9;
// Verify Logic, Check Constrains
// Overflow, Fits in Time/Memory ?
struct point
{
double x, y;
double dist(const point &other) const
{
double disSq = (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
return sqrt(disSq);
}
bool comp(const point &other) const
{
return fabs(x - other.x) < EPS && fabs(y - other.y) < EPS;
}
};
struct Node
{
point a, b;
bool comp(const Node &other) const
{
auto [c, d] = other;
double l = (a.y - b.y) * (c.x - d.x);
double r = (a.x - b.x) * (c.y - d.y);
return l == r;
}
double slope() const
{
if (a.y == b.y)
return 0;
if (a.x == b.x)
return inf;
double ret = (a.y - b.y) / (a.x - b.x);
return ret;
}
point intersect(const Node &other) const
{
if (comp(other)) // parallel
return {-inf, -inf};
double x = -1, y = -1;
int hx = 1, hy = 1;
// vertical line
if (slope() == inf)
x = a.x;
if (other.slope() == inf)
x = other.a.x, hx = 2;
// horizontal line
if (slope() == 0)
y = a.y;
if (other.slope() == 0)
y = other.a.y, hy = 2;
double c1 = a.y - slope() * a.x;
double c2 = other.a.y - other.slope() * other.a.x;
if (x == -1 && y == -1)
{
x = (c2 - c1) / (slope() - other.slope());
y = slope() * x + c1;
}
else if (x != -1)
{
if (hx == 1)
y = other.slope() * x + c2;
else
y = slope() * x + c1;
}
else if (y != -1)
{
if (hy == 1)
x = (y - c2) / other.slope();
else
x = (y - c1) / slope();
}
else
assert(false);
return {x, y};
}
};
void doWork()
{
int n;
cin >> n;
vector<Node> a(n);
for (int i = 0; i < n; i++)
{
point p1, p2;
cin >> p1.x >> p1.y >> p2.x >> p2.y;
a[i].a = p1, a[i].b = p2;
}
double ans = -1;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i].comp(a[j]))
continue;
for (int k = k + 1; k < n; k++)
{
if (a[i].comp(a[k]) || a[j].comp(a[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.comp(p2) || p1.comp(p3) || p2.comp(p3))
continue;
ans = max(ans, p1.dist(p2) + p1.dist(p3) + p2.dist(p3));
}
}
}
if (ans == -1)
cout << "no triangle";
else
cout << fixed << setprecision(10) << ans;
}
signed main()
{
zedanov int t = 1;
// cin >> t;
while (t--)
doWork();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3732kb
input:
3 0 0 0 1 0 0 1 0 0 1 1 0
output:
no triangle
result:
wrong answer