QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375098 | #3663. The Biggest Triangle | ChineseElNayem | WA | 7ms | 3928kb | C++23 | 2.0kb | 2024-04-02 21:29:55 | 2024-04-02 21:29:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct line{
long double x1,y1;
long double m=1e18,c;
bool isVer = 0;
};
struct point{
long double x,y;
};
point calc(line a, line b)
{
point ret;
if(a.isVer)
{
ret.x = a.x1;
ret.y = a.x1 * b.m + b.c;
}
else if(b.isVer)
{
ret.x = b.x1;
ret.y = b.x1 * a.m + a.c;
}
else
{
ret.x = (b.c - a.c) / (a.m - b.m);
ret.y = a.m * ret.x + a.c;
}
return ret;
}
long double dist(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
line lines[n];
for(int i = 0; i < n; i++)
{
long double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
lines[i].x1 = x1;
lines[i].y1 = y1;
if(x1 == x2)
{
lines[i].isVer = 1;
lines[i].m = 1e18;
continue;
}
lines[i].m = (y2 - y1) / (x2 - x1);
lines[i].c = -lines[i].m * x1 + y1;
}
long double ans = 0;
for(int a = 0; a < n; a++)
{
for(int b = a + 1; b < n; b++)
{
for(int c = b + 1; c < n; c++)
{
set<int> s;
s.insert(lines[a].m);
s.insert(lines[b].m);
s.insert(lines[c].m);
if(s.size() != 3)
continue;
point ab = calc(lines[a], lines[b]);
point bc = calc(lines[b], lines[c]);
point ca = calc(lines[a], lines[c]);
long double tdist = dist(ab, bc) + dist(bc, ca) + dist(ca, ab);
ans = max(ans, tdist);
}
}
}
if(ans)
cout << fixed << setprecision(10) << ans << '\n';
else
cout << "no triangle\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3808kb
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: 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: 3792kb
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: 1ms
memory: 3668kb
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: 7ms
memory: 3928kb
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:
510775.0347072321
result:
wrong answer