QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#365039#5067. Two WallshaoooWA 0ms3688kbC++143.6kb2024-03-24 18:33:122024-03-24 18:33:12

Judging History

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

  • [2024-03-24 18:33:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3688kb
  • [2024-03-24 18:33:12]
  • 提交

answer

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define ull unsigned long long
#define llf long double
using namespace std;
const llf eps=1e-10;
const llf Pi=acosl((llf)-1.0);
template<typename T>
inline void read(T &x){
    x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x=f?-x:x;
}
template<typename T>
inline void print(T x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
ll g(ll x){
    if(x>0) return 1;
    else if(x==0) return 0;
    else return -1;
}
int T;
struct line{
    ll xl,yl,xr,yr;
    void in(){
        scanf("%lld%lld%lld%lld",&xl,&yl,&xr,&yr);
    }
    ll dx(){return xr-xl;}
    ll dy(){return yr-yl;}
    void out(){
        printf("%lld %lld to %lld %lld\n",xl,yl,xr,yr);
    }
    llf length(){
        return (llf)sqrt((llf)(xr-xl)*(xr-xl)+(yr-yl)*(yr-yl));
    }
}l1,l2;
inline ll cross(line a,ll x,ll y){
    return (a.xr-a.xl)*(y-a.yl)-(a.yr-a.yl)*(x-a.xl);
}
bool NoInter(line a,line b){
    if(max(a.xl,a.xr)<min(b.xl,b.xr)||min(a.xl,a.xr)>max(b.xl,b.xr)||max(a.yl,a.yr)<min(b.yl,b.yr)||min(a.yl,a.yr)>max(b.yl,b.yr)) return true;
    if(g(cross(a,b.xl,b.yl))*g(cross(a,b.xr,b.yr))>0&&g(cross(b,a.xl,a.yl))*g(cross(b,a.xr,a.yr))>0) return true;
    return false;
}
bool Check(line a,line b){
    // puts("BEGIN");
    // a.out();b.out();
    
    line ac=(line){a.xl,a.yl,b.xl,b.yl};
    // cout<<"ac : ";ac.out();
    if(g(cross(ac,a.xr,a.yr))*g(cross(ac,b.xr,b.yr))<0) return false;
    llf anga=acos((llf)((llf)a.dx()*ac.dx()+a.dy()*ac.dy())/a.length()/ac.length());
    llf angb=acos((llf)((llf)-b.dx()*ac.dx()-b.dy()*ac.dy())/b.length()/ac.length());
    // cout<<anga<<" "<<angb<<"\n";
    if(anga+angb<Pi) return true;
    return false;
}
ll xa,ya,xb,yb;
ll x[4],y[4];

int main(){
    read(T);
    while(T--){
        read(xa),read(ya),read(xb),read(yb);
        l1.in();
        x[0]=l1.xl;x[1]=l1.xr;
        y[0]=l1.yl;y[1]=l1.yr;
        l2.in();
        x[2]=l2.xl;x[3]=l2.xr;
        y[2]=l2.yl;y[3]=l2.yr;
        line l=(line){xa,ya,xb,yb};
        if(NoInter(l,l1)&&NoInter(l,l2)){
            puts("0");
            continue;
        }
        vector<line> m,n;
        for(int i=0;i<=1;i++){
            line a=(line){xa,ya,x[i],y[i]};
            if(g(cross(a,x[2],y[2]))*g(cross(a,x[3],y[3]))>=0){
                m.push_back(a);
            }
            a.xl=xb,a.yl=yb;
            if(g(cross(a,x[2],y[2]))*g(cross(a,x[3],y[3]))>=0){
                n.push_back(a);
            }
        }
        for(int i=2;i<4;i++){
            line a=(line){xa,ya,x[i],y[i]};
            if(g(cross(a,x[0],y[0]))*g(cross(a,x[1],y[1]))>=0){
                m.push_back(a);
            }
            a.xl=xb,a.yl=yb;
            if(g(cross(a,x[0],y[0]))*g(cross(a,x[1],y[1]))>=0){
                n.push_back(a);
            }
        }
        bool f=0;
        for(int i=0;i<m.size();i++){
            for(int j=0;j<n.size();j++){
                if(Check(m[i],n[j])){
                    f=1;
                    break;
                }
            }
            if(f) break;
        }
        if(f) puts("1");
        else puts("2");
    }
    return 0;
}
/*
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

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
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: 0ms
memory: 3688kb

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
2

result:

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