QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99386#5679. Linked TrianglesjoesmittyWA 2ms3516kbC++206.7kb2023-04-22 08:26:472023-04-22 08:26:51

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:26:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3516kb
  • [2023-04-22 08:26:47]
  • 提交

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;

    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)) return true;
        }
    }

    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) * (w2/(w1 + w2)) + (tt - a) * (w1/(w1 + 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);
    }

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

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

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:

2
2 6
4 6

result:

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