QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714772 | #5679. Linked Triangles | zeyu# | WA | 0ms | 3932kb | C++23 | 5.4kb | 2024-11-06 06:54:50 | 2024-11-06 06:54:50 |
Judging History
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'