QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302497#5067. Two WallsFengfengWA 1ms3612kbC++202.4kb2024-01-10 22:26:592024-01-10 22:27:00

Judging History

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

  • [2024-01-10 22:27:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-01-10 22:26:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;


using db=long long;

struct point{
	db x,y;
	point(const db x1=0,const db y1=0):x(x1),y(y1){}
	point operator -(const point& w)const{
		return point(x-w.x,y-w.y);
	}
	point operator +(const point& w)const{
		return point(x+w.x,y+w.y);
	}
	db operator ^(const point& w)const{
		return x*w.y-y*w.x;
	}
	db operator |(const point& w)const{
		return x*w.x+y*w.y;
	}
	bool operator ==(const point& w)const{
		return x==w.x&&y==w.y;
	}
};

point p[6];//a b c d e f

int sign(db x){
	if(x==0) return 0;
	if(x<0) return -1;
	return 1;
}

struct Line{
	point s,e;
	Line(const point a=point(0,0),const point b=point(0,0)):s(a),e(b){}
	int onRight(const point &w)const{
		return sign(((e-s)^(s-w)));
	}
	bool on(const point &w)const{
		return sign((e-w)|(s-w))!=1&&sign((s-w)^(e-w))==0;
	}
};

//s e与w重合无效
bool cross(const Line x,const Line y){
	if(x.onRight(y.s)*x.onRight(y.e)>=0) return false;
	if(y.onRight(x.s)*x.onRight(x.e)>=0) return false;
	return true;
}

bool cross1(const Line x,const Line y){
	int sgn=sign((x.e-x.s)^(y.e-y.s));
	if(sgn==0) return false;
	return y.onRight(x.s)==-sgn&&x.onRight(y.s)==sgn;
}

void solve(){
	for(int i=0;i<6;i++){
		cin>>p[i].x>>p[i].y;
	}

	if(p[0]==p[1]){
		cout<<0<<'\n';
		return;
	}

	Line l1(p[0],p[1]),l2(p[2],p[3]),l3(p[4],p[5]);
	//a-b c-d e-f

	if(l1.on(p[2])||l1.on(p[3])||l1.on(p[4])||l1.on(p[5])){
		cout<<1<<'\n';
		return;
	}


	if(!cross(l1,l2)&&!cross(l1,l3)){
		cout<<0<<'\n';
		return;
	}

	if(!cross(l2,l3)){
		cout<<1<<'\n';
		return;
	}

	vector<point>s,s1;

	if(!cross(Line(p[0],p[2]),l3)){
		s.push_back(p[2]);
	}
	if(!cross(Line(p[0],p[3]),l3)){
		s.push_back(p[3]);
	}
	if(!cross(Line(p[0],p[4]),l2)){
		s.push_back(p[4]);
	}
	if(!cross(Line(p[0],p[5]),l2)){
		s.push_back(p[5]);
	}

	if(!cross(Line(p[1],p[2]),l3)){
		s1.push_back(p[2]);
	}
	if(!cross(Line(p[1],p[3]),l3)){
		s1.push_back(p[3]);
	}
	if(!cross(Line(p[1],p[4]),l2)){
		s1.push_back(p[4]);
	}
	if(!cross(Line(p[1],p[5]),l2)){
		s1.push_back(p[5]);
	}

	for(auto x:s){
		for(auto y:s1){
			if(x==y){
				cout<<1<<'\n';
				return;
			}
			if(cross1(Line(p[0],x),Line(p[1],y))){
				cout<<1<<'\n';
				return;
			}
		}
	}

	cout<<2<<'\n';
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3544kb

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: -100
Wrong Answer
time: 0ms
memory: 3612kb

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:

0
0

result:

wrong answer 1st numbers differ - expected: '2', found: '0'