QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109932#5679. Linked TrianglesTahsin13WA 2ms3716kbC++172.2kb2023-05-31 03:30:362023-05-31 03:30:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 03:30:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3716kb
  • [2023-05-31 03:30:36]
  • 提交

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"; 
}

详细

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'