QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55642 | #4497. Map | lqhsmash | AC ✓ | 267ms | 3768kb | C++ | 2.0kb | 2022-10-14 21:26:56 | 2022-10-14 21:26:57 |
Judging History
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;
}
详细
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