QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857214 | #9083. Two Ants | Nana7 | AC ✓ | 3ms | 4224kb | C++14 | 3.9kb | 2025-01-15 12:48:13 | 2025-01-15 12:48:14 |
Judging History
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,我给组数据试试?
详细
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