QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87563 | #3663. The Biggest Triangle | rania__# | WA | 5ms | 3628kb | C++14 | 5.0kb | 2023-03-13 17:45:26 | 2023-03-13 17:45:30 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5+7, P1 = 31, P2 = 37, mod= 1e9 + 7;
int mul(int a, int b) {
return (1LL * a * b) % mod;
}
int add(int a, int b) {
a = (a + mod) % mod;
b = (b + mod) % mod;
return (a + b) % mod;
}
int fp(int b, int p) {
if (b == 1 or p == 0)
return 1;
int ret = fp(b, p >> 1);
ret = mul(ret, ret);
if (p & 1)
ret = mul(ret, b);
return ret;
}
ll modInv(ll n) {
return fp(n, mod - 2);
}
ll fact[N], inv[N];
void pre() {
fact[0] = inv[0] = 1;
for (ll i = 1; i < N; i++)
fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}
ll nCr(ll n, ll r) {
return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
ll nPr(ll n, ll r) {
return ((fact[n] * inv[n - r])) % mod;
}
#define ld long double
int p =0;
pair<ld,ld> lineLineIntersection(pair<ld,ld> A, pair<ld,ld> B, pair<ld,ld> C, pair<ld,ld> D)
{
// Line AB represented as a1x + b1y = c1
double a1 = B.second - A.second;
double b1 = A.first - B.first;
double c1 = a1*(A.first) + b1*(A.second);
// Line CD represented as a2x + b2y = c2
double a2 = D.second - C.second;
double b2 = C.first - D.first;
double c2 = a2*(C.first)+ b2*(C.second);
double determinant = a1*b2 - a2*b1;
if (determinant == 0)
{
// The lines are parallel. This is simplified
// by returning a pair of FLT_MAX
p=1;
return make_pair(FLT_MAX, FLT_MAX);
}
else
{
double x = (b2*c1 - b1*c2)/determinant;
double y = (a1*c2 - a2*c1)/determinant;
return make_pair(x, y);
}
}
typedef complex<long double> point;
#define sz(a) ((int)(a).size())
#define all(n) (n).begin(),(n).end()
#define EPS 1e-9
#define OO 1e9
#define X real()
#define Y imag()
#define vec(a,b) ((b)-(a))
#define polar(r,t) ((r)*exp(point(0,(t))))
#define angle(v) (atan2((v).Y,(v).X))
#define length(v) ((long double)hypot((v).Y,(v).X))
#define lengthSqr(v) (dot(v,v))
#define dot(a,b) ((conj(a)*(b)).real())
#define cross(a,b) ((conj(a)*(b)).imag())
#define rotate(v,t) (polar(v,t))
#define rotateabout(v,t,a) (rotate(vec(a,v),t)+(a))
#define reflect(p,m) ((conj((p)/(m)))*(m))
#define normalize(p) ((p)/length(p))
#define same(a,b) (lengthSqr(vec(a,b))<EPS)
#define mid(a,b) (((a)+(b))/point(2,0))
#define perp(a) (point(-(a).Y,(a).X))
#define colliner pointOnLine
long double triangleArea3points(const point& a, const point& b, const point& c) {
return fabs(cross(a,b) + cross(b,c) + cross(c,a)) / 2;
}
ld distance(ld x1, ld y1, ld x2, ld y2)
{
// Calculating distance
return sqrt((x2 - x1)*(x2-x1) + (y2 - y1)*(y2-y1));
}
void doWork() {
int n;
cin >> n;
int x[n],y[n];
vector<pair<ld,ld>> pr(n),pr2(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
pr[i] = {x[i],y[i]};
cin >> x[i] >> y[i];
pr2[i] = {x[i],y[i]};
}
ld area = 0,mx=0;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
for (int k = j+1; k < n; ++k) {
p=0;
auto it = lineLineIntersection(pr[i],pr2[i],pr[j],pr2[j]);
if ( p == 1)
break;
p=0;
auto it2 = lineLineIntersection(pr[k],pr2[k],pr[j],pr2[j]);
if ( p == 1)
break;
p=0;
auto it3 = lineLineIntersection(pr[i],pr2[i],pr[k],pr2[k]);
if ( p == 1)
break;
point a = point(it.first,it.second);
point b = point(it2.first,it2.second);
point c = point(it3.first,it3.second);
ld temp = triangleArea3points(a,b,c);
if ( mx < temp)
{
mx = temp;
ld dist1 = distance(it.first,it.second,it2.first,it2.second);
ld dist2 = distance(it3.first,it3.second,it2.first,it2.second);
ld dist3 = distance(it.first,it.second,it3.first,it3.second);
area = max(area,dist1+dist2+dist3);
}
}
}
}
if ( area == 0)
{
cout <<"no triangle";
return;
}
cout << fixed << setprecision(10) << area << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("bisector.in","r",stdin);
// freopen("bisector.out","w",stdout);
int t = 1;
// cout << primes.size() << endl;
// cin >> t;
while (t--) {
doWork();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
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: 3304kb
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: 3528kb
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: 3332kb
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: 0
Accepted
time: 5ms
memory: 3628kb
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:
12352116.2772078642
result:
ok
Test #6:
score: -100
Wrong Answer
time: 4ms
memory: 3472kb
input:
100 -944 5551 -400 1443 504 -1168 1536 -466 1475 668 -404 -570 -390 -63 -1717 101 923 4554 -466 -1679 2307 566 1115 525 193 -48 -274 699 -3079 -3465 588 1087 -252 -1408 -1153 -24 4471 -1055 988 -373 48 248 -469 -1307 3143 2560 829 927 1079 -170 36 396 -1156 -2459 471 245 353 2927 752 1406 -3767 1685...
output:
2388391.6863131266
result:
wrong answer