QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#377160 | #5067. Two Walls | InfinityNS# | WA | 105ms | 3784kb | C++14 | 2.2kb | 2024-04-04 23:31:05 | 2024-04-04 23:31:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ll dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
int sgn(ll x){return x==0?0:(x<0?-1:1);}
bool OnSeg(pt A,pt B,pt C){
pt v=B-A;
ll da=dot(v,A);
ll dc=dot(v,C);
ll db=dot(v,B);
return da<=dc && dc<=db;
}
bool Good(pt A,pt B,pt C,pt D){
return sgn(cross(B-A,C-A))*sgn(cross(B-A,D-A))==-1;
}
bool SegInter(pt A,pt B,pt C,pt D){
if(Good(A,B,C,D) && Good(C,D,A,B))return true;
if(OnSeg(A,B,C) || OnSeg(A,B,D) || OnSeg(C,D,A) || OnSeg(C,D,B))return true;
return false;
}
bool RayInter(pt A,pt B,pt C,pt D){
return cross(B-A,D-C)>0;
}
pair<pt,pt> Tangents(pt A,pt B,vector<pt> pts){
vector<pt> L,R;
for(pt p:pts){
if(cross(B-A,p-A)>0)L.pb(p);
else R.pb(p);
}
pt bestL=L[0];
for(int i=1;i<L.size();i++){
if(cross(L[i]-A,bestL-A)<0){
bestL=L[i];
}
}
pt bestR=R[0];
for(int i=1;i<R.size();i++){
if(cross(R[i]-A,bestR-A)>0){
bestR=R[i];
}
}
//printf("tangents (%lld, %lld) (%lld, %lld)\n",bestL.x,bestL.y,bestR.x,bestR.y);
return {bestL,bestR};
}
pt read(){
int x,y;
scanf("%i %i",&x,&y);
return pt(x,y);
}
void Solve(){
pt A=read();
pt B=read();
pt C=read();
pt D=read();
pt E=read();
pt F=read();
bool sec1=SegInter(A,B,C,D);
bool sec2=SegInter(A,B,E,F);
bool pos=false,neg=false;
vector<pt> pts={C,D,E,F};
for(pt p:pts){
ll cr=cross(B-A,p-A);
if(cr<0)neg=true;
if(cr>0)pos=true;
}
if(A.x==B.x && A.y==B.y)printf("0\n");
else if(!sec1 && !sec2)printf("0\n");
else if(!sec1 || !sec2)printf("1\n");
else if(!pos || !neg)printf("1\n");
else{
pair<pt,pt> tg1=Tangents(A,B,pts);
pair<pt,pt> tg2=Tangents(B,A,pts);
if(RayInter(A,tg1.first,B,tg2.second)
|| RayInter(B,tg2.first,A,tg1.second)){
printf("1\n");
}else{
printf("2\n");
}
}
}
int main(){
int t;
scanf("%i",&t);
while(t--){
Solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
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: 3700kb
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: 3708kb
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: 105ms
memory: 3784kb
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:
1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 1st numbers differ - expected: '0', found: '1'