QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698566#5067. Two Wallswtz2333WA 88ms3756kbC++203.3kb2024-11-01 20:32:242024-11-01 20:32:25

Judging History

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

  • [2024-11-01 20:32:25]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:3756kb
  • [2024-11-01 20:32:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr double eps = 1e-7;
constexpr double PI = acos(-1);
constexpr double inf = 1e9;
struct Point { ll x, y; };        
using Vec = Point;                
struct Line { Point P; Vec v; };      
struct Seg { Point A, B; };           
Vec operator + (const Vec &a,const Vec &b){return (Vec){a.x + b.x,a.y + b.y};}
Vec operator - (const Vec &a,const Vec &b){return (Vec){a.x - b.x,a.y - b.y};}
ll operator * (const Point &a,const Point &b){return a.x * b.x + a.y * b.y;}// dot // 点乘
ll operator ^ (const Point &a,const Point &b){return a.x * b.y - a.y * b.x;}// cross  // 叉乘
bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}

ll dis(Point a,Point b) { return (a - b) * (a - b);}
int sgn(ll x){
    if(x == 0)
        return 0;
    if(x < 0)
        return -1;
    return 1;
}
Line line(Point A, Point B) { return {A, B - A}; }
// 线段与线段是否相交
bool cross_seg(Seg A,Seg B){ // 严格不交(不算端点)
    Point a = A.A,b = A.B,c = B.A,d = B.B;
    double c1 = (b - a) ^ (c - a),c2 = (b - a) ^ (d - a);
    double d1 = (d - c) ^ (a - c),d2 = (d - c) ^ (b - c);
    return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}

int cross_ray_ray(Line A,Line B) {
    if((A.v ^ B.v) == 0) {
       if(((A.P - B.P) ^ A.v) == 0) {
           if(sgn(A.v * (B.P - A.P)) < 0 && sgn(B.v * (A.P - B.P)) < 0) return -1;
           else return 0;
       }else return -1;
    }
    Vec v = B.P - A.P;
    ll c1 = v ^ A.v;
    ll c2 = v ^ B.v;
    ll c = A.v ^ B.v;
    if(sgn(c1) * sgn(c) >= 0 && sgn(c2) * sgn(c) >= 0) return 1; // 交
    return -1;
}
void solve() {
    Point A,B,C,D,E,F;
    cin >> A.x >> A.y >> B.x >> B.y;
    cin >> C.x >> C.y >> D.x >> D.y;
    cin >> E.x >> E.y >> F.x >> F.y;
    Seg s1 = {A,B};
    Seg s2 = {C,D};
    Seg s3 = {E,F};
    if(!cross_seg(s1,s2) && !cross_seg(s1,s3)) {
        cout << 0 << "\n";
        return ;
    }
    if(!cross_seg(s2,s3)) {
        cout << 1 << "\n";
        return ;
    }
    auto calc = [&](Point a) {
        if(sgn((E - C) ^ (D - C)) == sgn((a - C) ^ (D - C))) {
            if(sgn((C - E) ^ (F - E)) == sgn((a - E) ^ (F - E))) return 1;
            else return 2;
        }else {
            if(sgn((C - E) ^ (F - E)) == sgn((a - E) ^ (F - E))) return 4;
            else return 3;

        }
    };
    int flag1 = calc(A),flag2 = calc(B);
    if(abs(flag1 - flag2) != 2) {
        cout << 1 << "\n";
        return ;
    }
    if(flag1 > flag2) {
        swap(A,B);
        swap(flag1,flag2);
    }
    if(flag1 == 1) {
        Line l1 = line(A,C);
        Line l2 = line(A,E);
        Line l3 = line(B,F);
        Line l4 = line(B,D);
        if(cross_ray_ray(l1,l3) == 1 || cross_ray_ray(l2,l4) == 1) {
            cout << 1 << "\n";
            return ;
        }
    }else {
        Line l1 = line(A,E);
        Line l2 = line(A,D);
        Line l3 = line(B,C);
        Line l4 = line(B,F);
        if(cross_ray_ray(l1,l3) == 1 || cross_ray_ray(l2,l4) == 1) {
            cout << 1 << "\n";
            return ;
        }
    }
    cout << 2 << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 1
2 2 3 3
4 4 5 5
0 0
1 1
2 2 3 3
2 2 3 3
0 0
10 10
10 0 0 10
1 1 2 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2
-999999999 999999998
999999999 999999998
-1000000000 -1000000000 1000000000 1000000000
1000000000 -1000000000 -1000000000 1000000000
-999999999 999999998
999999999 999999998
-999999998 -999999998 1000000000 1000000000
999999998 -999999998 -1000000000 1000000000

output:

2
1

result:

ok 2 number(s): "2 1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

1
0 0
1 1
2 2 3 3
4 4 5 5

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 88ms
memory: 3684kb

input:

100000
-851839419 34688642
-667081997 395784949
-624068418 -155389155 119194510 -758711821
-992436155 -812775173 851861070 -592596572
974613003 -179673992
-485749861 520596304
-115838823 -265233646 -573799007 -222234500
608830643 -887109945 483106217 -906910755
-597593284 384264657
940783 476657007
...

output:

0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
1
...

result:

wrong answer 2811th numbers differ - expected: '1', found: '2'