QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87654 | #3663. The Biggest Triangle | Zuqa# | WA | 2ms | 3724kb | C++20 | 3.3kb | 2023-03-13 23:13:41 | 2023-03-13 23:13:45 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
#define x real()
#define y imag()
const int INF = 1e9;
const ld eps = 1e-8, pi = acos(-1);
int dcmp(ld a, ld b)
{
// a == b : 0
// a != b : != 0
// a > b : 1
// a < b : -1
// a >= b : != -1
// a <= b : != 1
return fabs(a - b) <= eps ? 0 : a < b ? -1 : 1;
}
ld cross(pt a, pt b)
{
return ((conj(a) * (b)).imag());
}
bool isCollinear(pt a, pt b, pt c)
{
return dcmp(cross(b - a, c - a), 0) == 0;
}
pt lineLineIntersection(pt A, pt B, pt C, pt D)
{
// Line AB represented as a1x + b1y = c1
ld a1 = B.y - A.y;
ld b1 = A.x - B.x;
ld c1 = A.x * B.y - B.x * A.y;
// Line CD represented as a2x + b2y = c2
ld a2 = D.y - C.y;
ld b2 = C.x - D.x;
ld c2 = C.x * D.y - D.x * C.y;
double determinant = a1 * b2 - a2 * b1;
if(determinant == 0)
{
// Same line aka Rakbin fo2 b3d
if(isCollinear(A, B, C) && isCollinear(A, B, D))
return pt(INF, INF);
// The lines are parallel.
return pt(-INF, -INF);
}
else
{
ld X = (b2 * c1 - b1 * c2) / determinant;
ld Y = (a1 * c2 - a2 * c1) / determinant;
return pt(X, Y);
}
}
ld solve(pt a, pt b, pt c)
{
return abs(a - b) + abs(a - c) + abs(b - c);
}
bool check(pt A)
{
if(A.x == INF && A.y == INF)
return false;
if(A.x == -INF && A.y == -INF)
return false;
return true;
}
void doWork()
{
int n;
cin >> n;
vector<pair<pt, pt>> v;
for(int i = 0, x1, y1, x2, y2; i < n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
v.push_back({pt(x1, y1), pt(x2, y2)});
}
ld ans = -100;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
pt A = lineLineIntersection(v[i].first, v[i].second, v[j].first, v[j].second);
if(!check(A))
continue;
for(int k = j + 1; j < n; j++)
{
pt B = lineLineIntersection(v[i].first, v[i].second, v[k].first, v[k].second);
pt C = lineLineIntersection(v[j].first, v[j].second, v[k].first, v[k].second);
if(!check(B) || !check(C) || isCollinear(A, B, C))
continue;
ans = max(ans, solve(A, B, C));
}
}
}
if(ans < 0)
cout << "no triangle";
else
cout << fixed << setprecision(12) << ans;
}
signed main()
{
FIO
int T = 1;
// cin >> T;
for(int i = 1; i <= T; i++)
doWork();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 0 0 0 1 0 0 1 0 0 1 1 0
output:
3.414213562373
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3452kb
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: 2ms
memory: 3660kb
input:
4 0 0 0 1 0 4 3 0 0 0 1 0 -1 -1 1 1
output:
12.000000000000
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3444kb
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: 2ms
memory: 3724kb
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:
12283563.651809119197
result:
wrong answer