QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109932 | #5679. Linked Triangles | Tahsin13 | WA | 2ms | 3716kb | C++17 | 2.2kb | 2023-05-31 03:30:36 | 2023-05-31 03:30:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct Point3d {
double x, y, z;
Point3d operator+(const Point3d& other) {
return Point3d {x+other.x, y+other.y, z+other.z};
}
Point3d operator-(const Point3d& other) {
return Point3d {x-other.x, y-other.y, z-other.z};
}
};
Point3d operator*(const Point3d& self, double t) {
return {t*self.x, t*self.y, t*self.z};
}
Point3d operator*(double t, const Point3d& self) {
return {t*self.x, t*self.y, t*self.z};
}
double dot(const Point3d& u, const Point3d& v) {
return u.x*v.x + u.y*v.y + u.z*v.z;
}
Point3d cross(const Point3d& u, const Point3d& v) {
return Point3d {u.y*v.z-v.y*u.z, u.x*v.z-v.x*u.z, u.x*v.y-v.x*u.y};
}
bool sameSide(Point3d& a, Point3d& b, Point3d& c, Point3d& p) {
Point3d u = cross(b-a, c-a);
Point3d v = cross(b-a, p-a);
return dot(u, v) >= 0;
}
bool insideTriangle(Point3d& a, Point3d& b, Point3d& c, Point3d& p) {
return sameSide(a, b, c, p) && sameSide(b, c, a, p) && sameSide(c, a, b, p);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Point3d points[6];
for(int i = 0; i < 6; ++i)
cin >> points[i].x >> points[i].y >> points[i].z;
vector<pair<int, int>> ans;
for(int i = 1; i < 6; ++i)
{
for(int j = i+1; j < 6; ++j)
{
int cur = 0;
Point3d other[3];
for(int k = 1; k < 6; ++k)
if(k != i && k != j)
other[cur++] = points[k];
Point3d u = points[i]-points[0];
Point3d v = points[j]-points[0];
Point3d n = cross(u, v);
bool ok = false;
for(int k = 0; k < 3 && !ok; ++k)
{
Point3d w = other[(k+1)%3]-other[k];
double t = dot(n, points[0]-other[k])/dot(n, w);
Point3d p = other[k]+t*w;
ok = ok || (0 <= t && t <= 1 && insideTriangle(points[0], points[i], points[j], p));
}
if(ok)
ans.push_back(make_pair(i+1, j+1));
}
}
cout<<ans.size()<<"\n";
for(auto p : ans)
cout<<p.first<<" "<<p.second<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
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: -100
Wrong Answer
time: 2ms
memory: 3716kb
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:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'