QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847452#9083. Two AntsAshleyAC ✓2ms4424kbC++173.6kb2025-01-07 23:27:342025-01-07 23:27:34

Judging History

This is the latest submission verdict.

  • [2025-01-07 23:27:34]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 4424kb
  • [2025-01-07 23:27:34]
  • Submitted

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