QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55642#4497. MaplqhsmashAC ✓267ms3768kbC++2.0kb2022-10-14 21:26:562022-10-14 21:26:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-14 21:26:57]
  • 评测
  • 测评结果:AC
  • 用时:267ms
  • 内存:3768kb
  • [2022-10-14 21:26:56]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e5 + 50;

int T = 1;
pair<int,int> a[10], b[10];

ll p2 (ll x) {
    return x * x;
}

ll dist2 (pair<int,int> x, pair<int,int> y) {
    ll res = (x.first - y.first) * (ll)(x.first - y.first);
    res += (x.second - y.second) * (ll)(x.second - y.second);
    return res;
}

void solve () {
    for (int i = 0; i < 4; i ++) 
        scanf ("%d%d", &a[i].first, &a[i].second);
    for (int i = 0; i < 4; i ++) 
        scanf ("%d%d", &b[i].first, &b[i].second);

    ll da = dist2 (a[0], a[1]), db = dist2 (b[0], b[1]);
    // printf("%lld %lld\n", da / __gcd (da, db), db / __gcd (da, db));

    ll a1 = 2ll * (a[3].first - a[0].first) * db 
            - 2ll * (b[3].first - b[0].first) * da;
    ll b1 = 2ll * (a[3].second - a[0].second) * db 
            - 2ll * (b[3].second - b[0].second) * da;
    ll c1 = (p2(a[0].first) + p2(a[0].second) - p2(a[3].first) - p2(a[3].second)) * db
            - (p2(b[0].first) + p2(b[0].second) - p2(b[3].first) - p2(b[3].second)) * da;
    
    ll a2 = 2ll * (a[0].first - a[2].first) * db 
            - 2ll * (b[0].first - b[2].first) * da;
    ll b2 = 2ll * (a[0].second - a[2].second) * db 
            - 2ll * (b[0].second - b[2].second) * da;
    ll c2 = (p2(a[2].first) + p2(a[2].second) - p2(a[0].first) - p2(a[0].second)) * db
            - (p2(b[2].first) + p2(b[2].second) - p2(b[0].first) - p2(b[0].second)) * da;

    // ll d = __gcd (a1, b1);
    // printf("%lld %lld %lld\n", a1 / d, b1 / d, c1 / d);
    // d = __gcd (a2, b2);
    // printf("%lld %lld %lld\n", a2 / d, b2 / d, c2 / d);

    double y = -1.0 * (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1);
    double x = -1.0 * (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);

    printf("%.9f %.9f\n", x, y);
}

int main () {
#ifdef LOCAL
    freopen ("in.in", "r", stdin);
    freopen ("out.out", "w", stdout);
#endif
    scanf ("%d", &T);
    while (T --) {
        solve ();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 267ms
memory: 3768kb

input:

100000
0 5
15 5
15 0
0 0
3 2
9 5
10 3
4 0
-605 604
604 605
605 -604
-604 -605
569 -338
568 -337
569 -336
570 -337
-964 963
963 964
964 -963
-963 -964
-364 838
-365 839
-364 840
-363 839
-664 663
663 664
664 -663
-663 -664
-307 -424
-308 -423
-307 -422
-306 -423
-866 865
865 866
866 -865
-865 -866
12...

output:

6.000000000 2.000000000
568.808264463 -336.251239669
-364.246369295 838.376037344
-306.450301205 -422.912650602
119.470554273 796.609122402
426.696564885 50.239821883
-138.701657459 -400.855248619
190.891911765 -43.827205882
-392.426023085 -700.838405037
96.510176391 624.641791045
576.278169014 448....

result:

ok 200000 numbers