QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714772#5679. Linked Triangleszeyu#WA 0ms3932kbC++235.4kb2024-11-06 06:54:502024-11-06 06:54:50

Judging History

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

  • [2024-11-06 06:54:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3932kb
  • [2024-11-06 06:54:50]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;

#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif

const ll mod = 1e9 + 7;

template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}

// Define a small epsilon for floating-point comparisons
const double EPSILON = 1e-8;

template<typename T>
struct Point {
    T x, y, z;

    // Overload subtraction operator
    Point operator-(const Point& p) const {
        return Point{x - p.x, y - p.y, z - p.z};
    }

    // Overload addition operator
    Point operator+(const Point& p) const {
        return Point{x + p.x, y + p.y, z + p.z};
    }

    // Overload scalar multiplication
    Point operator*(T scalar) const {
        return Point{x * scalar, y * scalar, z * scalar};
    }

    // Overload scalar division
    Point operator/(T scalar) const {
        return Point{x / scalar, y / scalar, z / scalar};
    }

    // Compute dot product
    T dot(const Point& p) const {
        return x * p.x + y * p.y + z * p.z;
    }

    // Compute cross product
    Point cross(const Point& p) const {
        return Point{
            y * p.z - z * p.y,
            z * p.x - x * p.z,
            x * p.y - y * p.x
        };
    }

    // Compute norm (magnitude)
    double norm() const {
        return sqrt(double(x * x + y * y + z * z));
    }
};

using point = Point<double>;

void dbg(point p){
	cout << p.x << ' ' << p.y << ' ' << p.z << '\n';
}

bool isPointInTriangle(const point& A, const point& B, const point& C, const point& P) {
    // Compute normal of the triangle's plane
    point N = (B - A).cross(C - A);

    // Check if point P lies in the plane of triangle ABC
    double plane_check = (P - A).dot(N);
    if (std::fabs(plane_check) > EPSILON)
        return false; // Point is not in the plane

    // Compute vectors
    point v0 = B - A;
    point v1 = C - A;
    point v2 = P - A;

    // Compute dot products
    double dot00 = v0.dot(v0);
    double dot01 = v0.dot(v1);
    double dot02 = v0.dot(v2);
    double dot11 = v1.dot(v1);
    double dot12 = v1.dot(v2);

    // Compute denominator
    double denom = dot00 * dot11 - dot01 * dot01;
    if (std::fabs(denom) < EPSILON)
        return false; // Triangle is degenerate

    // Compute barycentric coordinates
    double u = (dot11 * dot02 - dot01 * dot12) / denom;
    double v = (dot00 * dot12 - dot01 * dot02) / denom;

    // Check if point is inside the triangle
    return (u >= -EPSILON) && (v >= -EPSILON) && (u + v <= 1 + EPSILON);
}


bool linked(vector<point> t1, vector<point> t2){
	for (int i = 0; i < 3; i ++){
		point v = (t1[0] - t1[1]).cross(t1[0] - t1[2]);
		point p1 = t2[(i + 1) % 3], p2 = t2[(i + 2) % 3];
		if ((p1 - t1[0]).dot(v) > 0 && (p2 - t1[0]).dot(v) < 0 || (p1 - t1[0]).dot(v) < 0 && (p2 - t1[0]).dot(v) > 0){
			point le = p1, ri = p2;
			for (int _ = 0; _ < 100; _ ++){
				point mid = (le + ri) / 2;
				if ((p1 - t1[0]).dot(v) * (mid - t1[0]).dot(v) > 0){
					le = mid;
				} else{
					ri = mid;
				}
			}
			if (isPointInTriangle(t1[0], t1[1], t1[2], le)) return true;
		}
	}
	return false;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<point> a(6);
	for (int i = 0; i < 6; i ++){
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	set<pi> ans;
	for (int i = 0; i < (1 << 6); i ++){
		vector<point> t1, t2;
		for (int j = 0; j < 6; j ++){
			if ((i >> j) & 1) t1.push_back(a[j]);
			else t2.push_back(a[j]);
		}
		if (t1.size() != 3 || t2.size() != 3) continue;
		if (linked(t1, t2)){
			pi cur = {-1, -1};
			if (i & 1){
				for (int j = 1; j < 6; j ++){
					if ((i >> j) & 1){
						if (cur.fi == -1) cur.fi = j + 1;
						else cur.se = j + 1;
					}
				}
				ans.insert(cur);
			} else{
				for (int j = 1; j < 6; j ++){
					if (!((i >> j) & 1)){
						if (cur.fi == -1) cur.fi = j + 1;
						else cur.se = j + 1;
					}
				}
				ans.insert(cur);
			}
		}
	}
	cout << ans.size() << '\n';
	for (pi p : ans) cout << p.fi << ' ' << p.se << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

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: 0ms
memory: 3932kb

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:

3
2 6
3 4
4 6

result:

wrong answer 1st lines differ - expected: '1', found: '3'