QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726709#5679. Linked TrianglesNikaWA 1ms3984kbC++173.2kb2024-11-09 06:08:172024-11-09 06:08:17

Judging History

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

  • [2024-11-09 06:08:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3984kb
  • [2024-11-09 06:08:17]
  • 提交

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: 1ms
memory: 3980kb

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: 3824kb

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: 3816kb

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: 3788kb

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: 3984kb

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: 3760kb

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: 3744kb

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: 3788kb

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: 3748kb

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'