QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#857214#9083. Two AntsNana7AC ✓3ms4224kbC++143.9kb2025-01-15 12:48:132025-01-15 12:48:14

Judging History

This is the latest submission verdict.

  • [2025-01-15 12:48:14]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 4224kb
  • [2025-01-15 12:48:13]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define I inline
#define mkp make_pair
#define sgn dcmp
using namespace std; 

const double eps = 1e-8;
const double pi = 3.141592653;

struct point {
	double x,y;
	point(double xx=0,double yy=0) {
		x=xx; y=yy;
	}
};
typedef point Vector ;

inline point operator+(point a,Vector b){return point(a.x+b.x,a.y+b.y);}
inline Vector operator-(point a,point b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,double x){return Vector(a.x*x,a.y*x);}
inline Vector operator*(double x,Vector a){return Vector(a.x*x,a.y*x);}

I int dcmp(double x) {
	if(x<=-eps) return -1;
	if(x>=eps) return 1;
	return 0;
}
inline bool operator==(point a,point b) {return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
I double Len(point A) {
	return A.x*A.x+A.y*A.y;
}
I double dis(point A,point B) {
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
I double Cro(point A,point B) {
	return A.x*B.y-A.y*B.x;
}
I double Dot(point A,point B) {
	return A.x*B.x+A.y*B.y;
} 
I bool if_PS(point A,point B,point c) { //点和线段相交 
	return dcmp(Dot(A-c,B-c)<=0)&&dcmp(Cro(A-c,B-c)==0); //直线只用叉乘即可 
}
I bool if_LS(point A,point B,point c) {
	return dcmp(Cro(A-c,B-c)==0);
}
I bool if_SS(point A,point B,point C,point D) { //线段相交 (端点用if_PS) 
	double f1=Cro(A-C,A-B),f2=Cro(B-C,A-B),g1=Cro(C-A,C-D),g2=Cro(C-B,C-D);
	return ((dcmp(f1)<0)^(dcmp(f2)<0))&&((dcmp(g1)<0)^(dcmp(g2)<0));
}
I point LL(point A,point B,point C,point D) { //要先判定是否平行 
	point v=B-A,w=D-C,PQ=A-C;
	double t=Cro(PQ,w)/Cro(w,v);
	return A+t*v;
}
point retate(point a,double altha) //逆时针旋转
{
	return point(a.x * cos(altha) - a.y * sin(altha),a.x * sin(altha) + a.y *cos(altha));
}
I double dis_PL(point A,point B,point c) {
	return abs(Cro(A-c,B-c)/Len(A-B));
}
I point FootPoint(point A,point B,point p)//p在直线AB上的投影 
{
	point v = B - A;//方向向量v 
	return A + v * (Dot(p-A,v) / Dot(v,v));
}
I pair<double,point> dis_PS(point A,point B,point c) {
	if(Cro(A-B,c-B)<0) return mkp(dis(c,B),B);
	if(Cro(A-B,c-A)<0) return mkp(dis(c,A),A);
	return mkp(Cro(A-c,B-c)/dis(A,B),FootPoint(A,B,c));
}
I pair<double,point> dis_LS(point A,point B,point c) {
	return mkp(Cro(A-c,B-c)/dis(A,B),FootPoint(A,B,c));
} 

double angle(point O,point A,point B){//两向量OA,OB的夹角,OA -> OB逆时针为正 
	double ang = acos(Dot(A-O,B-O)/(dis(O,A)*dis(O,B)));
	if(Cro(A-O,B-O)<0) ang*=-1;
	return ang;
}

point w1,w2,b1,b2;
I void solve(int cas) {
	cout<<"Case "<<cas<<": ";
	cin>>w1.x>>w1.y>>w2.x>>w2.y;
	cin>>b1.x>>b1.y>>b2.x>>b2.y;
	b2=b2-w1; b1=b1-w1; w2=w2-w1; w1=point(0,0);
	double ang=angle(point(0,0),point(1,0),w2);
	w2=retate(w2,-ang); b1=retate(b1,-ang); b2=retate(b2,-ang);
	//cout<<w1.x<<' '<<w1.y<<' '<<w2.x<<' '<<w2.y<<' '<<b1.x<<' '<<b1.y<<' '<<b2.x<<' '<<b2.y<<endl;
	//有公共点 
	bool in1=if_PS(w1,w2,b1),in2=if_PS(w1,w2,b2);
	if(in1||in2) {
		if(sgn(Cro(w1-w2,b1-b2))==0) {
			cout<<0<<endl;
		} else {
			cout<<"inf"<<endl;
		}
		return ;
	}
	if(dcmp(b1.y)==0&&dcmp(b2.y)==0) {
		cout<<0<<endl;
		return ;
	}
	in1=if_PS(b1,b2,w1),in2=if_PS(b1,b2,w2);
//	cout<<"???"<<in1<<' '<<in2<<endl;
	if(in1||in2) {
		cout<<0<<endl;
		return ;
	}
	if(dcmp(b1.y)*dcmp(b2.y)==-1) {
		cout<<0<<endl;
		return ;
	}

	if(dcmp(b1.y)<=0&&dcmp(b2.y)<=0) b1.y=-b1.y,b2.y=-b2.y;
	if(w1.x>w2.x) swap(w1,w2);
	if(dcmp(Cro(b1,b2))>0) swap(b1,b2);
	
	
	if(sgn(Cro(b1-w1,b2-w2))==0) {
		//cout<<"casa"<<endl;
		//cout<<(b1-w1).x<<' '<<(b1-w1).y<<' '<<(b2-w2).x<<' '<<(b2-w2).y<<endl;
		cout<<"inf"<<endl;
		return ;
	}
	point sec=LL(w1,b1,w2,b2);
	if(dcmp(sec.y)>0) {
		cout<<"inf"<<endl;
	} else {
		double ans=fabs(Cro(w1-sec,w2-sec))/2;
		printf("%.10lf\n",ans);
	}
}
/*
3 3 2 8 2 9 2 1
*/
int main()
{
	int T; cin>>T;
	for(int i=1;i<=T;++i) solve(i);
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
1 1 1 2 0 0 0 3

output:

Case 1: inf
Case 2: 0
Case 3: 0.2500000000

result:

ok 9 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

27
0 0 2 2 1 1 1 -1
0 1 0 -1 0 0 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
0 0 1 0 0 0 0 1
-2 0 2 0 -1 1 1 2
-2 0 2 0 -1 1 1 1
-2 0 2 0 -1 1 3 1
-2 0 2 0 3 0 4 0
-1 1 1 1 -2 0 2 0
0 -2 2 -2 -2 0 2 0
0 -1 2 -1 -2 0 2 0
11 9 -1 20 7 -15 -6 -11
-19 -1 16 -1 11 7 -20 6
-5 -15 -19 5 9 -15 -12 15
15 9 -4 0 -17...

output:

Case 1: inf
Case 2: inf
Case 3: inf
Case 4: 0
Case 5: inf
Case 6: inf
Case 7: inf
Case 8: inf
Case 9: 0
Case 10: 1.0000000000
Case 11: 2.0000000000
Case 12: 1.0000000000
Case 13: inf
Case 14: inf
Case 15: 280.0000000000
Case 16: inf
Case 17: inf
Case 18: 15.8888888889
Case 19: inf
Case 20: 0
Case 21...

result:

ok 81 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 4224kb

input:

1000
-109 627 405 -683 431 435 -239 -644
-416 -797 -174 -217 473 -78 128 174
-150 222 -499 -601 543 -486 -523 862
-807 -905 636 -595 629 -537 -401 973
413 831 -826 -94 564 972 -855 -442
-23 580 272 -410 141 331 206 -390
-772 -874 -357 91 229 987 -590 167
-665 911 390 -273 -133 -223 910 112
-960 262 ...

output:

Case 1: 0
Case 2: 105447.4235058752
Case 3: 0
Case 4: inf
Case 5: 0
Case 6: 0
Case 7: 0
Case 8: 0
Case 9: 17985.2527279879
Case 10: 546679.2819311332
Case 11: inf
Case 12: inf
Case 13: 0
Case 14: 505636.1652141812
Case 15: inf
Case 16: inf
Case 17: 47057.8857985364
Case 18: inf
Case 19: 0
Case 20: i...

result:

ok 3000 tokens

Extra Test:

score: 0
Extra Test Passed