QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#820468#4497. MapSGColinAC ✓85ms3848kbC++201.7kb2024-12-18 21:32:482024-12-18 21:32:49

Judging History

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

  • [2024-12-18 21:32:49]
  • 评测
  • 测评结果:AC
  • 用时:85ms
  • 内存:3848kb
  • [2024-12-18 21:32:48]
  • 提交

answer

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

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

struct P {
    ll x, y;
} a, b, c, d, A, B, C, D;

inline ll sqr(ll w) {return w * w;}

ll a1, a2, b1, b2, c1, c2;

inline void work() {
    a.x = rd(); a.y = rd();
    b.x = rd(); b.y = rd();
    c.x = rd(); c.y = rd();
    d.x = rd(); d.y = rd();
    A.x = rd(); A.y = rd();
    B.x = rd(); B.y = rd();
    C.x = rd(); C.y = rd();
    D.x = rd(); D.y = rd();
    ll ab = sqr(a.x - b.x) + sqr(a.y - b.y);
    ll AB = sqr(A.x - B.x) + sqr(A.y - B.y);
    a1 = ab * (B.y - A.y) - AB * (b.y - a.y);
    b1 = AB * (b.x - a.x) - ab * (B.x - A.x);
    c1 = ab * ((B.y - A.y) * A.x - (B.x - A.x) * A.y) - AB * ((b.y - a.y) * a.x - (b.x - a.x) * a.y);
    //printf("%lld %lld %lld\n", a1, b1, c1);
    ll bc = sqr(c.x - b.x) + sqr(c.y - b.y);
    ll BC = sqr(C.x - B.x) + sqr(C.y - B.y);
    a2 = bc * (C.y - B.y) - BC * (c.y - b.y);
    b2 = BC * (c.x - b.x) - bc * (C.x - B.x);
    c2 = bc * ((C.y - B.y) * B.x - (C.x - B.x) * B.y) - BC * ((c.y - b.y) * b.x - (c.x - b.x) * b.y);
    //printf("%lld %lld %lld\n", a2, b2, c2);
    double y = (1.0 * c1 * a2 - 1.0 * c2 * a1) / (1.0 * b1 * a2 - 1.0 * a1 * b2);
    double x = (c1 - y * b1) / a1;
    printf("%.10lf %.10lf\n", x, y);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 85ms
memory: 3848kb

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.0000000000 2.0000000000
568.8082644628 -336.2512396694
-364.2463692946 838.3760373444
-306.4503012048 -422.9126506024
119.4705542725 796.6091224018
426.6965648855 50.2398218830
-138.7016574586 -400.8552486188
190.8919117647 -43.8272058824
-392.4260230850 -700.8384050367
96.5101763908 624.641791044...

result:

ok 200000 numbers