QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698537#5067. Two Wallswtz2333WA 1ms3688kbC++203.3kb2024-11-01 20:18:442024-11-01 20:18:46

Judging History

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

  • [2024-11-01 20:18:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3688kb
  • [2024-11-01 20:18:44]
  • 提交

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(abs(x) < eps)
        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((D - C) ^ (A - C)) > 0) {
            if(sgn((A - E) ^ (F - E)) > 0) return 1;
            else return 2;
        } else {
            if(sgn((A - E) ^ (F - E)) > 0) 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: 1ms
memory: 3688kb

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: -100
Wrong Answer
time: 1ms
memory: 3612kb

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:

1
1

result:

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