QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333399 | #5679. Linked Triangles | crimson231 | AC ✓ | 1ms | 3956kb | C++20 | 5.8kb | 2024-02-19 21:22:39 | 2024-02-19 21:22:40 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld INF = 1e17;
const ld TOL = 1e-7;
int N, M, T, Q, tmp[2]{ 0 };
bool V[6];
struct Seq {
ll x, y;
Seq(ll X = 0, ll Y = 0) : x(X), y(Y) {}
bool operator == (const Seq& s) const { return x == s.x && y == s.y; }
bool operator < (const Seq& s) const { return x == s.x ? y < s.y : x < s.x; }
void print() const { std::cout << x << " " << y << "\n"; return; }
}; std::vector<Seq> seq;
bool zero(const ld& x) { return std::abs(x) < TOL; }
struct Pos3D {
ld x, y, z;
Pos3D(ld X = 0, ld Y = 0, ld Z = 0): x(X), y(Y), z(Z) {}
bool operator == (const Pos3D& p) const { return zero(x - p.x) && zero(y - p.y) && zero(z - p.z); }
ld operator * (const Pos3D& p) const { return x * p.x + y * p.y + z * p.z; }
Pos3D operator / (const Pos3D& p) const {
Pos3D ret;
ret.x = y * p.z - z * p.y;
ret.y = z * p.x - x * p.z;
ret.z = x * p.y - y * p.x;
return ret;
}
Pos3D operator + (const Pos3D& p) const { return { x + p.x, y + p.y, z + p.z }; }
Pos3D operator - (const Pos3D& p) const { return { x - p.x, y - p.y, z - p.z }; }
Pos3D operator * (const ld& scalar) const { return { x * scalar, y * scalar, z * scalar }; }
Pos3D& operator += (const Pos3D& p) { x + p.x; y + p.y; z + p.z; return *this; }
Pos3D& operator *= (const ld& scalar) { x * scalar; y * scalar; z * scalar; return *this; }
ld mag() const { return sqrtl(x * x + y * y + z * z); }
} candi[6], MAXP{ INF, INF, INF };
std::vector<Pos3D> tri1, tri2;
struct Line3D {
Pos3D dir, p0;
Line3D(Pos3D DIR = Pos3D(0, 0, 0), Pos3D P0 = Pos3D(0, 0, 0)): dir(DIR), p0(P0) {}
};
struct Plane {
Pos3D norm, p0;
Plane(Pos3D NORM = Pos3D(0, 0, 0), Pos3D P0 = Pos3D(0, 0, 0)): norm(NORM), p0(P0) {}
};
Pos3D cross(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) / (d3 - d2); }
ld dot(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) * (d3 - d2); }
bool on_seg_strong(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) {
ld ret = dot(d1, d3, d2);
return zero(cross(d1, d2, d3).mag()) && (ret > 0 || zero(ret));
}
bool on_seg_weak(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) {
ld ret = dot(d1, d3, d2);
return zero(cross(d1, d2, d3).mag()) && ret > 0;
}
Line3D L(const Pos3D& p1, const Pos3D& p2) { return { p2 - p1, p1 }; }
Plane P(const Pos3D& p1, const Pos3D& p2, const Pos3D& p3) {
Pos3D norm = (p2 - p1) / (p3 - p2);
return Plane(norm, p1);
}
Plane P(std::vector<Pos3D> tri) {
Pos3D& p1 = tri[0], p2 = tri[1], p3 = tri[2];
Pos3D norm = (p2 - p1) / (p3 - p2);
return Plane(norm, p1);
}
Pos3D intersection(const Plane& S, const Line3D& l) {
ld det = S.norm * l.dir;
if (zero(det)) return { INF, INF, INF };
ld t = (S.norm * S.p0 - S.norm * l.p0) / det;
return l.p0 + (l.dir * t);
}
int inner_check(std::vector<Pos3D> H, const Pos3D& p) {
int sz = H.size();
if (sz <= 1) return -1;
if (sz == 2) {
if (on_seg_strong(H[0], H[1], p)) return 0;
else return -1;
}
Plane S = P(H);
Pos3D norm = S.norm;
Pos3D torque1 = cross(H[0], H[1], p);
for (int i = 1; i < sz; i++) {
Pos3D cur = H[i], nxt = H[(i + 1) % sz];
Pos3D torqueI = cross(cur, nxt, p);
if (zero(torqueI.mag())) {
if (on_seg_strong(cur, nxt, p)) return 0;
else return -1;
}
if (torque1 * torqueI < 0) return -1;
}
return 1;
}
bool brute(const Seq& s) {
bool IN = 0, OUT = 0;
Plane TRI2 = P(tri2);
for (int i = 0; i < 3; i++) {
Pos3D cur = tri1[i], nxt = tri1[(i + 1) % 3];
Pos3D inx = intersection(TRI2, L(cur, nxt));
if (inx == MAXP) continue;
if (on_seg_weak(cur, nxt, inx) || cur == inx) {
if (inner_check(tri2, inx) == 1) IN = 1;
if (inner_check(tri2, inx) == -1) OUT = 1;
}
}
if (IN == 1 && OUT == 1) seq.push_back({ s });
return IN && OUT;
}
void dfs(int depth = 0, int idx = 1) {
if (depth == 2) {
int n = 0;
tri2.clear();
for (int j = 1; j < 6; j++) {
if (V[j]) tmp[n++] = j;
if (!V[j]) tri2.push_back(candi[j]);
}
brute(Seq(tmp[0] + 1, tmp[1] + 1));
return;
}
for (int i = idx; i < 6; i++) {
if (!V[i]) {
tri1.push_back(candi[i]);
V[i] = 1;
dfs(depth + 1, i + 1);
tri1.pop_back();
V[i] = 0;
}
}
return;
}
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
for (int i = 0; i < 6; i++) std::cin >> candi[i].x >> candi[i].y >> candi[i].z;
tri1.push_back(candi[0]); V[0] = 1;
dfs();
std::sort(seq.begin(), seq.end());
int sz = seq.size();
std::cout << sz << "\n";
for (int i = 0; i < sz; i++) seq[i].print();
return;
}
int main() { solve(); return 0; }//boj27861 Linked Triangles
//struct Pos {
// ll x, y;
// Pos(ll X = 0, ll Y = 0) : x(X), y(Y) {}
// bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
// bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
// Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
// Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
// Pos operator * (const ll& n) const { return { x * n, y * n }; }
// Pos operator / (const ll& n) const { return { x / n, y / n }; }
// ll operator * (const Pos& p) const { return { x * p.x + y * p.y }; }
// ll operator / (const Pos& p) const { return { x * p.y - y * p.x }; }
// Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
// Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
// Pos& operator *= (const ll& scale) { x *= scale; y *= scale; return *this; }
// Pos& operator /= (const ll& scale) { x /= scale; y /= scale; return *this; }
// Pos operator ~ () const { return { -y, x }; }
// ll operator ! () const { return x * y; }
// ld mag() const { return hypot(x, y); }
// void print() const { std::cout << x << " " << y << "\n"; return; }
//};
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3704kb
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: 1ms
memory: 3720kb
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: 3956kb
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: 1ms
memory: 3776kb
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: 1ms
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: 1ms
memory: 3788kb
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: 3716kb
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: 0
Accepted
time: 1ms
memory: 3792kb
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:
1 3 6
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
5.8832 4.2308 -0.5738 -3.3329 7.0130 -6.9039 -8.7819 7.5500 -3.0628 -8.2697 -2.8331 -8.3711 7.4996 3.2136 -7.4336 -4.5882 -2.4783 -1.6155
output:
3 2 4 2 6 3 4
result:
ok 4 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
7.6850 5.2805 9.4561 5.6332 -4.3292 -1.5505 8.4928 3.1573 2.9439 -3.4751 4.2336 -6.2825 2.0533 1.5089 -5.1904 1.9290 7.1246 -5.6887
output:
1 5 6
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
-6.4631 -6.0018 -8.3013 -4.2504 -1.9595 0.0015 9.1460 -9.8983 1.9107 -1.3431 -4.4299 -8.9080 8.8338 4.5798 -4.8447 -9.5794 9.2495 -1.9444
output:
1 3 5
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
8.1098 8.7662 -0.5323 -2.7080 1.0147 9.3257 3.3181 -6.7925 -0.2656 -6.2061 -3.7029 6.6701 4.8109 0.9043 -7.7916 8.2971 9.3408 7.4590
output:
1 4 6
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
0.7030 -4.2527 -3.3542 4.9892 4.6405 0.1936 6.4665 3.6603 -0.7573 -2.7292 -9.5903 2.4434 2.1488 4.7420 -1.6722 1.4563 -2.9071 0.0344
output:
1 2 4
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
2.2889 5.7114 -3.2417 6.2896 -9.2879 -7.6487 8.2127 0.8676 5.0007 0.4564 0.7301 6.3646 -1.3067 3.2770 -3.7341 4.1332 -0.8919 3.0173
output:
1 4 6
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
2.2900 -9.7090 -8.5439 8.0837 7.1754 -5.7574 5.5256 -7.1201 -1.8606 -0.3155 4.7771 0.0365 1.5703 8.1374 -1.9806 5.2074 5.9649 4.9484
output:
3 2 4 2 6 5 6
result:
ok 4 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
-6.4601 4.3204 7.3006 7.8092 -4.2867 3.3257 -3.0653 -2.2210 4.2164 -9.4836 -8.0321 -7.2147 -4.4158 -8.7707 8.1745 3.6565 7.4014 5.1368
output:
1 2 4
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
-4.6283 -7.3800 4.9382 6.0522 -4.6880 -5.6545 -9.7257 4.1153 2.0589 -0.5804 -6.0445 -9.3820 4.9191 0.4055 9.1288 5.2645 -6.2096 0.3280
output:
3 2 3 2 5 4 5
result:
ok 4 lines
Test #19:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
1.6735 0.7915 3.4557 -8.6249 -2.1781 7.2110 9.9849 0.8844 4.1306 7.2401 8.6278 -4.6113 9.4239 -5.7525 4.7497 9.6454 4.1612 1.1931
output:
1 5 6
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
5.2341 -3.0318 -9.1944 -5.8134 0.1070 3.9918 -3.2804 8.4528 6.6702 7.9394 9.5833 6.9070 -3.8144 -3.6164 -4.7621 1.1059 2.9455 9.5251
output:
1 2 3
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
-1.8943 -5.1851 -4.0217 4.9502 4.1022 -9.9857 -6.8457 4.8856 5.9649 -4.6211 -2.1717 5.9769 -8.7984 -2.6598 -2.0037 -8.4303 -7.5469 -6.4235
output:
1 4 5
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
7.9195 6.4394 0.3951 9.0419 -7.7326 -5.9354 -0.8932 -5.5514 -7.2127 -3.5689 4.0074 7.3452 -2.6154 -3.7425 2.1830 -4.4288 -8.1715 1.7615
output:
1 3 6
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
3.2933 -0.1218 -6.5570 5.3489 2.9165 -7.4639 0.8178 -5.3210 7.7209 9.8004 1.3036 -3.7399 1.3227 3.0378 7.2653 -7.1111 -8.4844 6.4210
output:
1 4 5
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
1.4225 5.3619 -6.7873 2.9499 -9.0353 -0.2296 -6.2206 -7.0195 4.1848 -2.7755 0.9867 5.2128 9.6494 6.1635 -6.6496 -9.7593 -2.1909 -2.9135
output:
1 2 3
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
-6.9537 -3.4442 5.1607 -0.1657 1.2895 9.0296 0.8678 3.3507 -3.7537 9.9973 -4.0755 -2.0537 -6.6049 2.6974 -5.2174 0.0799 8.4297 -2.6491
output:
1 3 6
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
-8.3444 -5.5013 -8.1463 6.3489 -4.8776 -2.2804 3.0889 -5.2444 -4.6936 -8.4036 2.2604 -7.6446 8.4213 3.5109 8.4365 4.7077 9.6175 -3.7947
output:
1 2 4
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
3.8723 -8.9602 2.1167 -9.9734 -5.5953 7.7640 8.8383 7.7135 -7.6538 -5.4866 6.5595 1.6564 1.8371 2.6273 2.5534 3.6605 6.8036 6.1923
output:
1 4 6
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
-6.2893 -2.7872 1.2822 -4.4563 8.1937 -7.7488 2.3549 -6.7210 9.6031 2.4225 5.5183 -7.2111 3.5653 4.8626 2.5859 -0.7371 6.9050 2.4314
output:
1 4 5
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
-8.2571 0.3790 0.5212 -6.4419 7.5129 -1.1452 -0.1440 1.4809 -6.9502 -1.5524 -2.0594 6.4582 -3.4961 8.8344 9.4882 9.7382 9.2265 -6.2893
output:
3 3 5 4 6 5 6
result:
ok 4 lines
Test #30:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
2.2798 7.0880 4.4285 9.6110 1.6666 7.4605 -5.3077 -9.0711 -6.9948 -3.7607 -1.7572 0.2891 2.5287 -9.1059 4.9583 0.3704 -0.5527 0.8149
output:
1 5 6
result:
ok 2 lines