QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#847452 | #9083. Two Ants | Ashley | AC ✓ | 2ms | 4424kb | C++17 | 3.6kb | 2025-01-07 23:27:34 | 2025-01-07 23:27:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e6+5;
const double eps=1e-8;
struct point{
double x,y;
point(double a=0,double b=0):x(a),y(b){}
void input(){scanf("%lf%lf",&x,&y);}
void output(){printf("point: %.3f %.3f\n",x,y);}
friend point operator-(const point &a,const point &b)
{
return point(a.x-b.x, a.y-b.y);
}
friend point operator*(const point &a,const double k)
{
return point(a.x*k, a.y*k);
}
friend point operator/(const point &a,const double k)
{
return point(a.x/k, a.y/k);
}
friend bool operator==(const point &a,const point &b)
{
return fabs(a.x-b.x)<eps && fabs(a.y-b.y)<eps;
}
double norm()const
{
return sqrt(x*x+y*y);
}
};
double det(const point &a,const point &b)
{
return a.x*b.y - a.y*b.x;
}
double dot(const point &a,const point &b)
{
return a.x*b.x + a.y*b.y;
}
point rotate_point(const point &p,double A)
{
return point(p.x*cos(A)-p.y*sin(A), p.x*sin(A)+p.y*cos(A));
}
point interSect(const point &a,const point &b,const point &c,const point &d)
{
double s1=det(c-a,b-a);
double s2=det(d-a,b-a);
return (c*s2-d*s1)/(s2-s1);
}
point B[2],W[2];
void deout()
{
B[0].output(); B[1].output(); W[0].output(); W[1].output();
puts("");
}
double solve()
{
if(B[0].y>B[1].y)swap(B[0],B[1]); //使得B[0]在下
//平移,使得B[0]为原点
W[0]=W[0]-B[0];
W[1]=W[1]-B[0];
B[1]=B[1]-B[0];
B[0]=B[0]-B[0];
//旋转,使得B[1]在y轴上
double sinxz=det(point(0,1),B[1])/B[1].norm();
double A = -asin(sinxz); //取负的,转回去
B[1]=rotate_point(B[1],A);
W[0]=rotate_point(W[0],A);
W[1]=rotate_point(W[1],A);
if(fabs(W[0].x)<eps || fabs(W[1].x)<eps) //w有端点在y轴上
{
if(fabs(W[0].x)<eps && fabs(W[1].x)<eps) //两端均在y轴
return 0;
point iny = fabs(W[0].x)<eps ? W[0] : W[1];
if(eps<iny.y && iny.y<B[1].y-eps) //一端在B内
return 0;
return -1; //w有一端在y轴上,但不在B内
}
//W与B不平行
if(fabs(W[0].x-W[1].x)>eps)
{
point sec = interSect(W[0],W[1], B[0],B[1]);
if(eps<sec.y && sec.y<B[1].y-eps) return 0; //W或W的延长线穿过B
}
//W跨过y轴
if(W[0].x*W[1].x<-eps)return -2;
//此处考虑W两端点 和B两端点怎么连
double sinw0 = det(W[0],W[1])/W[0].norm()/W[1].norm();
if(W[0].x>eps && sinw0<-eps || W[0].x<-eps && sinw0>eps)swap(W[0],W[1]);
//有可能W与B对应端点相连,是平行向量
if(fabs( det(W[0]-B[0],W[1]-B[1]) )<eps)return -3;
point sec = interSect(B[0],W[0], B[1],W[1]);
if(sec.x*W[0].x<eps)return -4; //交点和W在y两侧,inf
double s = det(sec-W[0],sec-W[1])/2;
return fabs(s);
}
int main()
{
int cas=0,T;
for(cin>>T;T--;)
{
W[0].input();
W[1].input();
B[0].input();
B[1].input();
printf("Case %d: ",++cas);
double ans=solve();
if(ans<-0.5)puts("inf");
else printf("%.10f\n",ans);
}
}
/**
1 -2 0 -1 0 0 0 10
inf
3 2 1 5 6 2 4 78
Case 4: 3.1849315068
9 1 9 6 5 6 9 4
(inf)
1 4 0 5 5 0 6 0
0.00
3 2 4 2 5 3 5 8
0.750000
4 8 6 9 4 1 3 6
5.250000
4 4 8 4 3 3 7 4
inf
2 4 3 4 8 5 6 4
0.000000
1 9 9 1 5 5 1 4
inf
4 3 4 4 4 6 2 9
0.000000
3 3 2 8 2 9 1 2
0
3 3 2 8 2 9 2 1
0.000
1 4 4 3 4 4 8 3
inf 这组特殊inf,最好画画
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4172kb
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.0000000000 Case 3: 0.2500000000
result:
ok 9 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 4424kb
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.0000000000 Case 5: inf Case 6: inf Case 7: inf Case 8: inf Case 9: 0.0000000000 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: ...
result:
ok 81 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 4196kb
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.0000000000 Case 2: 105447.4235058751 Case 3: 0.0000000000 Case 4: inf Case 5: 0.0000000000 Case 6: 0.0000000000 Case 7: 0.0000000000 Case 8: 0.0000000000 Case 9: 17985.2527279879 Case 10: 546679.2819311328 Case 11: inf Case 12: inf Case 13: 0.0000000000 Case 14: 505636.1652141830 Case 15: ...
result:
ok 3000 tokens
Extra Test:
score: 0
Extra Test Passed