QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#820468 | #4497. Map | SGColin | AC ✓ | 85ms | 3848kb | C++20 | 1.7kb | 2024-12-18 21:32:48 | 2024-12-18 21:32:49 |
Judging History
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