QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87653 | #3663. The Biggest Triangle | Zuqa# | WA | 1ms | 3572kb | C++20 | 3.3kb | 2023-03-13 23:10:37 | 2023-03-13 23:10:40 |
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-12, 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: 1ms
memory: 3572kb
input:
3 0 0 0 1 0 0 1 0 0 1 1 0
output:
3.414213562373
result:
ok
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3528kb
input:
3 0 0 0 1 0 0 1 0 0 0 1 1
output:
NO TRIANGLE
result:
wrong answer