QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87563#3663. The Biggest Trianglerania__#WA 5ms3628kbC++145.0kb2023-03-13 17:45:262023-03-13 17:45:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-13 17:45:30]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3628kb
  • [2023-03-13 17:45:26]
  • 提交

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;
}

詳細信息

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