QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#365036 | #5067. Two Walls | haooo | WA | 1ms | 4072kb | C++14 | 3.6kb | 2024-03-24 18:32:17 | 2024-03-24 18:32:18 |
Judging History
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: 0
Wrong Answer
time: 1ms
memory: 4072kb
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 BEGIN 0 0 to 10 0 10 10 to 10 0 0.785398 0.785398 1
result:
wrong output format Expected integer, but "BEGIN" found