QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717930#5067. Two WallszjjwsWA 117ms3928kbC++146.9kb2024-11-06 19:18:112024-11-06 19:18:16

Judging History

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

  • [2024-11-06 19:18:16]
  • 评测
  • 测评结果:WA
  • 用时:117ms
  • 内存:3928kb
  • [2024-11-06 19:18:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// #define LD double//需要的话换longdouble
using LD = long double;
const LD eps=1e-14;
const LD epss=1e-7;
const LD PI=acos(-1.0);
int sgns(LD x){return (x>epss)-(x<-epss);}
int sgn(LD x){return (x>eps)-(x<-eps);}
LD sqr(LD x){return x*x;}

LD rad_to_deg(LD r){return r*180.0/PI;}
LD deg_to_rad(LD r){return r*PI/180.0;}

struct PT
{
    LD x,y;
    PT(){x=0;y=0;}
    PT(LD x,LD y):x(x),y(y){}
    PT operator -(const PT &a)const {return PT(x-a.x,y-a.y);}
    PT operator +(const PT &a)const {return PT(x+a.x,y+a.y);}

    PT operator *(const LD a)const {return PT(x*a,y*a);}
    friend PT operator *(const LD &a,const PT &b){return PT(a*b.x,a*b.y);}
    PT operator /(const LD a)const {return PT(x/a,y/a);}

    PT perp(){return PT(-y,x);}//逆时针90度
    LD arg(){return atan2(y,x); }//辐角(-pi,pi]
    LD norm(){return sqrt(x*x+y*y);}//模长 
    LD norm2(){return x*x+y*y;}//模长平方
    PT truncate(LD r)//长度变为r
    {
        LD k=norm();
        if(sgn(k)==0)return *this;
        r/=k;
        return PT(x*r,y*r);
    }
};
LD det(PT a,PT b){return a.x*b.y-a.y*b.x;}
LD dot(PT a,PT b){return a.x*b.x+a.y*b.y;}
LD Edis(PT a,PT b){return sqrt(sqr((a.x-b.x))+sqr((a.y-b.y)));}
LD Edis2(PT a,PT b){return sqr((a.x-b.x))+sqr((a.y-b.y));}
bool operator ==(PT a,PT b)
{
    return sgn(Edis2(a,b))==0;
}
int orientation(PT a, PT b, PT c) { return sgn(det(b-a,c-a));}
PT perp(PT a) { return PT(-a.y, a.x);}//逆时针90
PT perp3(PT a) { return PT(a.y, -a.x); }//顺时针90
PT rotatel(PT a, LD t) //逆时针
{
    return PT(a.x*cos(t)-a.y*sin(t),a.x*sin(t)+a.y*cos(t));
}
PT rotater(PT a, LD t) //顺时针
{
    return PT(a.x*cos(t)+a.y*sin(t),-a.x*sin(t)+a.y*cos(t));
}

const LD LS=-1.0;
const LD RS=1.0;
LD get_angle(PT a,PT b)//两向量夹角
{
    return acos(max(LS,min(RS,dot(a,b)/a.norm()/b.norm())));
}
PT midPT(PT a,PT b){return PT((a.x+b.x)/2.0,(a.y+b.y)/2.0);}//中点

LD S(PT a,PT b,PT c)//三角形面积
{
    return abs(det(a-b,a-c));
}
LD S(vector<PT>&a)//按逆时针顺序给出
{
    if(a.size()<3)return 0;
    LD ans=0;
    for(int i=0;i<a.size();i++)ans+=det(a[i],a[(i+1)%a.size()]);
    return ans;
}
bool turn_left(PT a,PT b)//向量b是不是在向量a左边
{
    return sgn(det(a,b))>0;
}

vector<PT>get_convex(vector<PT>a)//最好不要引用a,因为可能a的顺序有用
{
    if(a.size()<=2)return a;
    PT st=a[0];
    for(auto p:a)if(p.x<st.x||(p.x==st.x&&p.y<st.y))st=p;
    sort(a.begin(),a.end(),[&](PT u,PT v){
        int s=sgn(det(u-st,v-st));//1 为v在u左侧
        return s!=0?s>0:Edis(u,st)<Edis(v,st);//一条直线上的情况
    });
    vector<PT>ret;ret.clear();
    for(auto p:a)
    {
        for(;ret.size()>1&&!turn_left(ret[ret.size()-1]-ret[ret.size()-2],p-ret[ret.size()-2]);)ret.pop_back();
        ret.push_back(p);
    }
    return ret;
}

struct line//表示射线的时候a,b分别是起终
{
    PT s,t;
    line(){s=PT(0,0);t=PT(0,0);}
    line(PT s,PT t):s(s),t(t){}
};
//射线同或反方向
bool same_or_contro_dir(line l1,line l2)
{
    return sgn(det(l1.t-l1.s,l2.t-l2.s))==0;
}
//射线同方向
bool same_dir(line l1,line l2)
{
    return sgn(det(l1.t-l1.s,l2.t-l2.s))==0&&sgn(dot(l1.t-l1.s,l2.t-l2.s))>0;
}

//点在直线上
bool point_on_line(PT p,line l)
{
    return sgn(det(p-l.s,p-l.t))==0;
}
//点在线段上
bool point_on_segment(PT p,line l)
{
    return sgn(det(p-l.s,p-l.t))==0&&sgn(dot(p-l.s,p-l.t))<=0;
}
bool point_on_segment_2(PT p,line l)
{
    return sgn(det(p-l.s,p-l.t))==0&&sgn(dot(p-l.s,p-l.t))<=0&&(!(p==l.s))&&(!(p==l.t));
}
//两点在直线两端(不在直线上)
bool two_side(PT p1,PT p2,line l)
{
    return sgn(det(p1-l.s,l.t-l.s))*sgn(det(p2-l.s,l.t-l.s))<0;
}
//线段判交
bool segment_cross(line l1,line l2)
{
    if(point_on_segment(l1.s,l2)||point_on_segment(l1.t,l2)||point_on_segment(l2.s,l1)||point_on_segment(l2.t,l1))
    return true;
    return two_side(l1.s,l1.t,l2)&&two_side(l2.s,l2.t,l1);
}
//线段判交(不在端点)
bool segment_cross_2(line l1,line l2)
{
    return two_side(l1.s,l1.t,l2)&&two_side(l2.s,l2.t,l1);
}
//直线判交,0不交,1交 ,2重合
int line_cross(line l1,line l2)
{
    if(same_or_contro_dir(l1,l2))
    {
        if(point_on_line(l1.s,l2))return 2;
        return 0;
    }
    return 1;
}
//重合的情况要特殊考虑一下(比如特殊的线段和射线)
PT line_cross_PT(line l1,line l2)
{
    LD u=det(l1.t-l1.s,l2.s-l1.s);
    LD v=-det(l1.t-l1.s,l2.t-l1.s);
    return (l2.s*v+l2.t*u)/(u+v);
}

//射线判交,0不交,1交 ,2重合

PT ray_cross_tmp;
int ray_cross(line l1,line l2)
{
    int s=line_cross(l1,l2);
    if(s==0)return s;
    if(s==2)
    {
        if(sgn(dot(l1.s-l2.s,l2.t-l2.s))<0&&sgn(dot(l2.s-l1.s,l1.t-l1.s))<0)
        return 0;
        return 2;
    }
    ray_cross_tmp=line_cross_PT(l1,l2);
    // printf("PT:(%.4Lf %.4Lf)\n",ray_cross_tmp.x,ray_cross_tmp.y);
    //在两条射线方向上
    return sgn(dot(ray_cross_tmp-l1.s,l1.t-l1.s))>=0&&sgn(dot(ray_cross_tmp-l2.s,l2.t-l2.s))>=0;
}

PT A,B,C,D,E,F;
void read(PT &p)
{
    int x,y;scanf("%d%d",&x,&y);
    p=PT(x,y);
}


int tag[4];
PT p[4];

void work()
{
    read(A);read(B);read(C);read(D);read(E);read(F);
    if(!segment_cross(line(A,B),line(C,D))&&!segment_cross(line(A,B),line(E,F))){puts("0");return;}
    if(!segment_cross(line(C,D),line(E,F))){puts("1");return;}
    p[0]=C;p[1]=D;p[2]=E;p[3]=F;
    for(int i=0;i<2;i++)
    {
        if(point_on_segment(p[i],line(E,F))){puts("1");return;}
    }
    for(int i=2;i<4;i++)
    {
        if(point_on_segment(p[i],line(C,D))){puts("1");return;}
    }

    if(point_on_line(A,line(C,D))&&point_on_line(B,line(C,D))){puts("1");return;}
    if(point_on_line(A,line(C,E))&&point_on_line(B,line(C,E))){puts("1");return;}
    if(point_on_line(A,line(E,F))&&point_on_line(B,line(E,F))){puts("1");return;}
    if(point_on_line(A,line(F,D))&&point_on_line(B,line(F,D))){puts("1");return;}
    if(C==D||E==F){puts("1");return;}
    for(int i=0;i<4;i++)for(int j=0;j<4;j++)
    {
        if(ray_cross(line(A,p[i]),line(B,p[j]))==1)
        {
            PT mid=ray_cross_tmp;
            // printf("%d %d %d %d\n",segment_cross(line(A,mid),line(C,D)),segment_cross(line(A,mid),line(E,F)),segment_cross(line(B,mid),line(C,D)),segment_cross(line(B,mid),line(E,F)));
            if(segment_cross_2(line(A,mid),line(C,D))||segment_cross_2(line(A,mid),line(E,F)))continue;
            if(segment_cross_2(line(B,mid),line(C,D))||segment_cross_2(line(B,mid),line(E,F)))continue;
            // printf("i:%d j:%d\n",i,j);
            puts("1");
            return;
        }
    }
    puts("2");
    return;
}
int main()
{
    int T;scanf("%d",&T);
    for(;T-->0;)work();
    return 0;
}
/*
1
-4 0
4 0
-1 0 0 0
1 0 2 0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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: 117ms
memory: 3604kb

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 652nd numbers differ - expected: '1', found: '2'