QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#681047 | #7065. Triangle | cabbagea | TL | 902ms | 3872kb | C++17 | 3.4kb | 2024-10-27 00:28:20 | 2024-10-27 00:28:21 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
tuple<int, int, int> dir(PII a, PII b) {
tuple<int, int, int> res = { b.x - a.x, b.y - a.y, 0 };
auto &[dx, dy, k] = res;
if ( dx == 0 && dy == 0 ) return res;
k = __gcd( abs(dx), abs(dy) );
dx /= k, dy /= k;
return res;
}
int check( tuple<int, int, int> d1, tuple<int, int, int> d2 ) {
auto &[dx1, dy1, k1] = d1;
auto &[dx2, dy2, k2] = d2;
if ( dx1 == dx2 && dy1 == dy2 ) {
if ( k1 * 2 < k2 ) return 1;
else if ( k1 < k2 ) return 2;
else return 0;
}
return 0;
}
int cymbal(PII a, PII b, PII c) {
return abs( a.x * ( b.y - c.y ) + b.x * ( c.y - a.y ) + c.x * ( a.y - b.y ) );
}
double cymbal(PDD a, PDD b, PDD c) {
return abs( a.x * ( b.y - c.y ) + b.x * ( c.y - a.y ) + c.x * ( a.y - b.y ) );
}
PDD cabbagea( PII p1, PII p2, tuple<int, int, int> d, int s ) {
auto &[dx, dy, k] = d;
PDD pp1 = { p1.x, p1.y }, pp2 = { p2.x, p2.y };
double l = 0, r = k;
while (true) {
double m = ( l + r ) / 2;
PDD res = { (double)p2.x + m * dx, (double)p2.y + m * dy };
double dist = cymbal(pp1, pp2, res) * 2 - s;
if ( abs(dist) < 1e-6 ) return res;
else if ( dist > 0 ) r = m;
else l = m;
}
return { 0, 0 };
}
void solve() {
PII p1, p2, p3, p;
cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p.x >> p.y;
auto d12 = dir(p1, p2), d13 = dir(p1, p3), d23 = dir(p2, p3);
auto d21 = dir(p2, p1), d31 = dir(p3, p1), d32 = dir(p3, p2);
cout << fixed << setprecision(12);
if ( p == p1 ) {
cout << ( p2.x + p3.x ) * 0.5 << ' ' << ( p2.y + p3.y ) * 0.5 << endl;
} else if ( p == p2 ) {
cout << ( p1.x + p3.x ) * 0.5 << ' ' << ( p1.y + p3.y ) * 0.5 << endl;
} else if ( p == p3 ) {
cout << ( p1.x + p2.x ) * 0.5 << ' ' << ( p1.y + p2.y ) * 0.5 << endl;
} else if ( p.x * 2 == p1.x + p2.x && p.y * 2 == p1.y + p2.y ) {
cout << p3.x << ' ' << p3.y << endl;
} else if ( p.x * 2 == p1.x + p3.x && p.y * 2 == p1.y + p3.y ) {
cout << p2.x << ' ' << p2.y << endl;
} else if ( p.x * 2 == p2.x + p3.x && p.y * 2 == p2.y + p3.y ) {
cout << p1.x << ' ' << p1.y << endl;
} else {
auto d1p = dir(p1, p), d2p = dir(p2, p);
int c12 = check(d1p, d12), c13 = check(d1p, d13), c23 = check(d2p, d23);
if ( c12 == 0 && c13 == 0 && c23 == 0 ) {
cout << -1 << endl;
return;
}
PDD ans;
int s = cymbal(p1, p2, p3);
if ( c12 == 1 ) {
ans = cabbagea(p, p2, d23, s);
} else if ( c12 == 2 ) {
ans = cabbagea(p, p1, d13, s);
} else if ( c13 == 1 ) {
ans = cabbagea(p, p3, d32, s);
} else if ( c13 == 2 ) {
ans = cabbagea(p, p1, d12, s);
} else if ( c23 == 1 ) {
ans = cabbagea(p, p3, d31, s);
} else if ( c23 == 2 ) {
ans = cabbagea(p, p2, d21, s);
}
cout << ans.x << ' ' << ans.y << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
2 0 0 1 1 1 0 1 0 0 0 1 1 1 0 2 0
output:
0.500000000000 0.500000000000 -1
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 900ms
memory: 3872kb
input:
999966 9456 15557 18451 3957 6242 20372 9855 5351 30245 31547 9979 4703 25914 19144 26670 11383 13855 0 24614 0 15860 11017 12445 0 27870 17680 4219 3554 9129 29072 28316 17893 3249 27269 12754 4923 31746 16860 14894 21576 6846 0 1915 0 25023 28721 10508 0 10110 11862 23224 10373 17715 8212 29474 11...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21424.681479417726 13086.053910984208 -1 -1 18711.237990304096 10162.376377258697 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 28212.952134892665 245.817786238793 -1 -1 -1 -1 -1 -1 -1 -1 22604.575302188769 14546.128716105784 -1 -1 115...
result:
ok 1111378 numbers
Test #3:
score: 0
Accepted
time: 902ms
memory: 3860kb
input:
999974 9228 16833 13143 23461 5117 7645 21359 13652 21313 3160 20333 1620 16288 7781 13315 10132 4372 0 27536 0 3207 8695 9983 0 21469 29998 19948 29904 30517 11141 14857 12881 11116 29172 16833 32095 18915 9448 22043 12275 32131 0 14304 0 16638 29018 2048 0 4695 4823 14130 2496 32676 4092 6363 2476...
output:
-1 -1 11482.990372016144 5737.223836381258 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15409.841854934608 12451.427863654373 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10828.971385779587 25347.334857322996 -1 -1 -1 -1 -1 18768.672699464689 12151.367150989892 -1 -1 -1...
result:
ok 1110866 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
1000000 54242 34392 23333 92971 5711 47765 54242 34392 24492 41078 36756 68794 2060 62118 14678 50283 12685 18891 59613 23256 26016 46755 59613 23256 85238 49611 95092 85360 45143 87657 95092 85360 72852 37174 39825 60628 32289 18423 72852 37174 95309 61613 1645 45877 78395 38196 95309 61613 92215 7...
output:
14522.000000000000 70368.000000000000 32900.888888888905 68052.222222222219 19350.500000000000 32823.000000000000 65190.500000000000 68634.000000000000 36057.000000000000 39525.500000000000 40020.000000000000 42036.500000000000 95183.500000000000 40970.500000000000 28582.000000000000 94834.500000000...