QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377152#5067. Two WallsInfinityNS#WA 102ms3996kbC++142.1kb2024-04-04 23:18:522024-04-04 23:18:52

Judging History

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

  • [2024-04-04 23:18:52]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:3996kb
  • [2024-04-04 23:18:52]
  • 提交

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(!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;
}

详细

Test #1:

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

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

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

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

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'