QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99387#5679. Linked TrianglesjoesmittyAC ✓2ms3656kbC++207.0kb2023-04-22 08:32:572023-04-22 08:33:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-22 08:33:00]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3656kb
  • [2023-04-22 08:32:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  =  998244353;
#define inf 1e18;
#define INF INT_MAX

long double PI = 4*atan(1);
long double eps = 1e-12;


template<class T> struct Point3D {
	typedef Point3D P;
	typedef const P& R;
	T x, y, z;
	explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
	bool operator<(R p) const {
		return tie(x, y, z) < tie(p.x, p.y, p.z); }
	bool operator==(R p) const {
		return tie(x, y, z) == tie(p.x, p.y, p.z); }
	P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
	P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
	P operator*(T d) const { return P(x*d, y*d, z*d); }
	P operator/(T d) const { return P(x/d, y/d, z/d); }
	T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
	P cross(R p) const {
		return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
	}
	T dist2() const { return x*x + y*y + z*z; }
	double dist() const { return sqrt((double)dist2()); }
	//Azimuthal angle (longitude) to x-axis in interval [-pi, pi]
	double phi() const { return atan2(y, x); } 
	//Zenith angle (latitude) to the z-axis in interval [0, pi]
	double theta() const { return atan2(sqrt(x*x+y*y),z); }
	P unit() const { return *this/(T)dist(); } //makes dist()=1
	//returns unit vector normal to *this and p
	P normal(P p) const { return cross(p).unit(); }
	//returns point rotated 'angle' radians ccw around axis
	P rotate(double angle, P axis) const {
		double s = sin(angle), c = cos(angle); P u = axis.unit();
		return u*dot(u)*(1-c) + (*this)*c - cross(u)*s;
	}

    
};



typedef Point3D<long double> P;
std::ostream& operator<<(std::ostream& o, P p) {
    return o << p.x << " " << p.y<< " " << p.z;
}
vector<P> pnts;

bool inTri(P x, P a, P b, P c) {
    P ba = b - a;
    P ca = c - a;
    P norm = ba.normal(ca);

    P cb = c - b;
    P ac = a - c;

    int side1 = ((x - a).cross(ba)).dot(norm) > 0;
    int side2 = ((x - b).cross(cb)).dot(norm) > 0;
    int side3 = ((x - c).cross(ac)).dot(norm) > 0;

   // cout << side1 << " " << side2 << " " << side3 << endl;

    return (side1 == side2 && side2 == side3);
}

bool linked(int idx1, int idx2, int idx3, int idx4, int idx5) {
  //  cout << idx1 << " " << idx2 << endl;
    P a = pnts[0];
    P b = pnts[idx1];
    P c = pnts[idx2];

    
    P d = pnts[idx3];
    P e = pnts[idx4];
    P f = pnts[idx5];
    vector<P> T = {d,e,f};

    P ba = b - a;
    P ca = c - a;
    P norm = ba.normal(ca);


    FOR(i,0,3) {
        if(abs((T[i] - a).dot(norm)) < eps && inTri(T[i], a,b,c)) {
        //    cout << "HI " << i << endl;
            P t1 = T[(i + 1) % 3];
            P t2 = T[(i + 2) % 3];
            
            int side1 = (t1 - a).dot(norm) > 0;
            int side2 = (t2 - a).dot(norm) > 0;
            if(side1 == side2) continue;

            ld v1 = (t1 - a).dot(norm);
            ld v2 = (t2 - a).dot(norm);
            P m = a + (t1 - a) * (abs(v2)/(abs(v1) + abs(v2))) + (t2 - a) * (abs(v1)/(abs(v1) + abs(v2)));
            if(!inTri(m, a,b,c)) {
              //  cout << "x " << i << endl;
                return true;
            }
        }
    }

  //  cout << norm << endl;
    FOR(i,0,3) {
        P t1 = T[i];
        P t2 = T[(i + 1)%3];
        P t3 = T[(i + 2)%3];

        int side1 = (t1 - a).dot(norm) > 0;
        int side2 = (t2 - a).dot(norm) > 0;
        if(side1 == side2) continue;

        // cout << "BYE " << i << endl;

        ld v1 = (t1 - a).dot(norm);
        ld v2 = (t2 - a).dot(norm);
        // cout << t1 << endl;
        // cout << t2 << endl;
        // cout << a << endl;
        // cout << v1 << " " << v2 << endl;
        // cout << (t1 - a) * (v2/(abs(v1) + abs(v2))) << endl;
        // cout << (t2 - a) * (v1/(abs(v1) + abs(v2))) << endl;
        P m = a + (t1 - a) * (abs(v2)/(abs(v1) + abs(v2))) + (t2 - a) * (abs(v1)/(abs(v1) + abs(v2)));
        // cout << "m: " <<  m << endl;

        if(!inTri(m, a,b,c)) continue;

        int side3 = (t3 - a).dot(norm) > 0;


        P tt = (side3 == side2) ? t1 : t2;

        ld w1 = (t3 - a).dot(norm);
        ld w2 = (tt - a).dot(norm);
        m = a + (t3 - a) * (abs(w2)/(abs(w1) + abs(w2))) + (tt - a) * (abs(w1)/(abs(w1) + abs(w2)));
        
        
        if(!inTri(m, a,b,c)) {
            return true;
        }
    }

   // cout << idx1 << " " << idx2 << " " << idx3 << " " << idx4 << " " << idx5 << endl;


    return false;
}

int main() {
    auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif  
    
    FOR(i,0,6) {
        ld x,y,z; cin >> x >> y >> z;
        P p(x,y,z);
        pnts.pb(p);
    }

    linked(3,5,1,2,4);

    vector<pii> ans;
    FOR(i,1,6) {
        FOR(j,i+1,6) {
            vi notin; 
            FOR(k,1,6) if(k != i && k != j) notin.pb(k);
            if(linked(i,j, notin[0], notin[1], notin[2])) {
                ans.pb({i+1, j+1});
            }
        }
    }   

    cout << ans.size() << endl;
    for(auto x : ans) {
        cout << x.ff << " " << x.ss << endl;
    }


    



    
    
    // auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    // cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3580kb

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: 2ms
memory: 3620kb

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: 2ms
memory: 3600kb

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

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: 3644kb

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: 2ms
memory: 3516kb

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: 2ms
memory: 3624kb

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: 2ms
memory: 3516kb

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: 2ms
memory: 3648kb

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: 2ms
memory: 3584kb

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: 2ms
memory: 3596kb

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: 2ms
memory: 3620kb

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: 2ms
memory: 3640kb

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: 2ms
memory: 3588kb

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: 1ms
memory: 3624kb

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: 2ms
memory: 3520kb

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: 2ms
memory: 3512kb

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: 2ms
memory: 3584kb

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: 2ms
memory: 3620kb

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: 2ms
memory: 3480kb

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: 1ms
memory: 3596kb

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: 2ms
memory: 3640kb

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: 2ms
memory: 3596kb

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: 2ms
memory: 3592kb

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: 2ms
memory: 3592kb

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: 2ms
memory: 3656kb

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: 2ms
memory: 3600kb

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: 2ms
memory: 3484kb

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: 3520kb

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: 2ms
memory: 3484kb

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