QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718301 | #5067. Two Walls | zjjws | WA | 102ms | 3748kb | C++14 | 7.0kb | 2024-11-06 20:13:14 | 2024-11-06 20:13:14 |
Judging History
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(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: 1ms
memory: 3680kb
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: 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 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3748kb
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: 102ms
memory: 3616kb
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 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 15th numbers differ - expected: '1', found: '0'