hdu6398 计算几何

时间：2024-07-20 12:36:08

不算严格的计算几何，就是各种分类

精度调好就能过，考虑三条边斜着放的所有情况即可

#include<bits/stdc++.h>

#define LL long long

#define ll long long

#define fi first

#define se second

#define mk make_pair

#define pi acos(-1)

#define PII pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

#define g(ans) printf("%.12f\n",ans)

#define bug puts("####")

using namespace std;

const double eps=1e-6;

const int N = 2e5 + 7;

const int M = 1e7 + 7;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +7;

double a,b,c,w,ans;

double getang(double a,double b,double c)

{

    return acos((b*b+c*c-a*a)/(2.0*c*b));

}

void cal()

{

    double ang2=getang(c,a,b);

    double ang1=getang(b,a,c);

    double ang3=getang(a,b,c);

//    printf("%.12f %.12f %.12f\n",a,b,c);

    if(ang1<=pi/2+eps&&ang2<=pi/2+eps&&a<=w+eps)ans=min(ans,sin(ang1)*c);

    if(ang1+eps>=pi/2&&c*cos(pi-ang1)+a<=w+eps)ans=min(ans,c*sin(pi-ang1));

    double ang4=asin(w/b);

    if(ang4+eps>=ang3&&pi/2-ang4+eps>=ang2)ans=min(ans,b*cos(ang4));

    double ang5=asin(w/a)+ang1-pi/2;

    if(ang5+eps>=0&&ang5<=pi/2+eps&&a>w+eps&&asin(w/a)+eps>=ang2)

        ans=min(ans,sin(ang5)*c+a*cos(asin(w/a)));

    if(ang2+eps>=pi/2&&b*cos(pi-ang2)+a<=w+eps)ans=min(ans,b*sin(pi-ang2));

    ang4=asin(w/c);

    if(ang4+eps>=ang3&&pi/2-ang4+eps>=ang1)ans=min(ans,c*cos(ang4));

    ang5=asin(w/a)+ang2-pi/2;

    if(ang5+eps>=0&&ang5<=pi/2+eps&&a>w+eps&&asin(w/a)+eps>=ang1)

        ans=min(ans,sin(ang5)*b+a*cos(asin(w/a)));

}

void solve()

{

    double d[10];

    for(int i=0;i<6;i++)scanf("%lf",&d[i]);

    scanf("%lf",&w);

    a=sqrt((d[0]-d[2])*(d[0]-d[2])+(d[1]-d[3])*(d[1]-d[3]));

    b=sqrt((d[0]-d[4])*(d[0]-d[4])+(d[1]-d[5])*(d[1]-d[5]));

    c=sqrt((d[4]-d[2])*(d[4]-d[2])+(d[5]-d[3])*(d[5]-d[3]));

    ans=1e18;

    cal();

    swap(a,b);swap(b,c);cal();

    swap(a,b);swap(b,c);cal();

    if(ans>=1e18)puts("impossible");

    else printf("%.12lf\n",ans);

}

int main()

{

//    freopen("b.in","r",stdin);

//    freopen("b.out","w",stdout);

    int T;scanf("%d",&T);

    while(T--)solve();

    return 0;

}

/**********************

1

2 4 0 2 7 4 4

6.08

**********************/

相关文章