QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726710 | #5679. Linked Triangles | Nika | WA | 0ms | 3960kb | C++17 | 3.2kb | 2024-11-09 06:09:07 | 2024-11-09 06:09:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using pii = pair<int, int>;
const ld EPS = 1e-7;
struct P3{
ld x, y, z;
P3() {
this->x = 0; this->y = 0; this->z = 0;
}
explicit P3(ld x, ld y, ld z) {
this->x = x;
this->y = y;
this->z = z;
}
ld dot(P3 v){
return v.x*this->x + v.y*this->y + v.z*this->z;
}
P3 cross(P3 v) {
return P3(this->y*v.z - this->z*v.y, this->z*v.x - this->x*v.z, this->x*v.y - this->y*v.x);
}
};
P3 operator-(P3 l, const P3& r) {
return P3(l.x - r.x, l.y - r.y, l.z - r.z);
}
P3 operator+(P3 l, const P3& r) {
return P3(l.x + r.x, l.y + r.y, l.z + r.z);
}
void solve() {
vector<P3> a(6);
for (int i = 0; i < 6; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
vector<pii> ans;
for (int b = 0; b < (1<<6); b++) {
int cnt = 0;
vector<int> T1;
vector<int> T2;
vector<P3> t1;
vector<P3> t2;
for (int i = 0; i < 6; i++) {
if (b & (1<<i)) {
t1.push_back(a[i]);
T1.push_back(i);
}
else {
t2.push_back(a[i]);
T2.push_back(i);
}
}
if (t1.size() != 3) continue;
P3 A = t1[0];
for (int i = 0; i < 3; i++) {
t1[i] = t1[i] - A;
t2[i] = t2[i] - A;
}
P3 normal = t1[1].cross(t1[2]);
// edge intersection
int noedges = 0;
cnt = 0;
for (int i = 0; i < 3; i++) {
int j= (i+1)%3;
P3 edge = t2[j] - t2[i];
ld t = -1*(t2[i].dot(normal))/(edge.dot(normal));
if (t > 0) {
P3 intp = t2[i] + P3(t*edge.x, t*edge.y, t*edge.z);
// check if intp is in t1
int sidescnt = 0;
for (int k = 0; k < 3; k++) {
int l = (k+1)%3;
P3 r = (t1[l] - intp).cross(t1[k] - intp);
sidescnt += (r.dot(normal) > 0);
}
sidescnt %= 3;
if (sidescnt > 0) continue;
noedges++;
}
}
if (noedges == 1) {
if (b & 1) {
ans.emplace_back(min(T1[1], T1[2])+1, max(T1[1], T1[2])+1);
}
continue;
}
// one vertex lies in the interior
bool good = false;
for (int i = 0; i < 3; i++) {
if (abs(t2[i].dot(normal)) > EPS) continue;
P3 intp = t2[i];
// check if intp is in t1
int sidescnt = 0;
for (int k = 0; k < 3; k++) {
int l = (k+1)%3;
P3 r = (t1[l] - intp).cross(t1[k] - intp);
sidescnt += (r.dot(normal) > 0);
}
sidescnt %= 3;
if (sidescnt > 0) continue;
vector<bool> thingy;
for (int j = 0; j < 3; j++) {
if (j == i) continue;
// if ((t2[j] - t2[i]).dot(normal) == 0) continue;
thingy.push_back((t2[j] - t2[i]).dot(normal) > 0);
}
if (thingy.size() != 2) continue;
if (thingy[0] == thingy[1]) continue;
good = true;
break;
}
if (good) {
if (b & 1) {
ans.emplace_back(min(T1[1], T1[2])+1, max(T1[1], T1[2])+1);
}
continue;
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for (pii x : ans) {
cout << x.first << ' ' << x.second << endl;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
1 0 0 -1 0 0 0 1 0.2 0 -1 0.2 0.2 0.2 1 0.2 0.2 -1
output:
3 2 3 2 5 3 4
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
-7.8212 6.0669 8.5429 6.8601 5.7125 6.4651 -1.4178 7.0540 -0.0678 3.3535 -0.2770 1.2726 -2.4538 -5.0173 1.3681 0.5774 -4.3039 -5.4755
output:
1 4 6
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
-0.7297 0.1660 8.8249 0.2927 -7.0325 6.5672 8.8653 8.8948 3.6222 -7.0054 5.8303 9.7899 -5.2537 2.5352 -9.9275 0.0807 -4.4782 -5.9199
output:
1 2 5
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
-0.6478 8.5319 4.8899 -0.3780 -5.7694 -5.9423 -1.7597 4.0013 -4.0520 6.7414 -3.4843 7.1844 6.8234 -8.6367 -2.1165 9.0166 -6.8566 -6.5933
output:
1 2 5
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
-8.1542 -3.5082 -9.4465 7.5776 -4.0828 -6.4696 -8.0569 8.8116 -5.2878 -6.7636 -2.1570 5.8144 1.6530 -7.3579 9.3215 -2.9592 3.0434 -9.9900
output:
1 5 6
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
-1.4895 -9.2239 4.9174 -1.2844 -5.8982 -7.2312 -8.3142 5.2566 2.7348 9.8243 3.4760 -7.7570 3.0870 -8.5288 -1.3170 -0.7327 -3.4846 -3.6615
output:
1 4 6
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
2.6602 -6.6905 -3.7999 -5.5756 8.0805 -7.6713 -1.2337 -8.1267 -2.1753 -8.7845 -1.5313 -1.7837 -9.6123 -9.6594 3.7709 -3.8460 7.7783 6.5572
output:
3 2 5 4 5 4 6
result:
ok 4 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
-3.4596 -6.1669 5.8628 6.7265 -6.3462 -0.4187 7.3097 3.7265 -8.8461 -0.8005 -3.0356 -5.0364 -9.1143 -4.2919 -0.2931 3.4024 9.6496 -8.3551
output:
1 4 6
result:
ok 2 lines
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3788kb
input:
-2.7245 -1.7476 -5.5523 0.3886 0.5709 2.4341 1.8639 7.1395 5.1457 -5.6447 -4.8931 1.3328 2.2310 -0.9524 -5.4822 2.5867 -3.9042 3.7924
output:
2 3 4 3 6
result:
wrong answer 1st lines differ - expected: '1', found: '2'