2021牛客多校賽第二場

傳送門

A

B

C水題

D水題

E

F計算幾何求兩球的體積并

G動态規劃

H

I模拟bfs

J

K模拟貪心

L

F（計算幾何）

題意：三維坐标系，給4個點A、B、C、D的坐标以及K1和K2兩個數，滿足|AX|>=K1*|BX|的點X形成集合，滿足|CY|>=K2*|DY|的點Y形成集合。求X集合與Y集合并集的體積

解析：首先當然需要知道X集合與Y集合大緻長什麼樣子，推導式子很容易得知其實兩個集合都是球，且可以得知球的球心與半徑。那麼之後就是求兩個球的體積交了，套闆子即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi=acos(-1.0);
 
double x[5],y[5],z[5];
 
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        for(int i=1;i>=0;i--)
        {
            cin >> x[i] >> y[i] >> z[i];
        }
        for(int i=3;i>=2;i--)
        {
            cin >> x[i] >> y[i] >> z[i];
        }
        double k1, k2;
        cin >> k1 >> k2;
        double ab=sqrt((x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1])+(z[0]-z[1])*(z[0]-z[1]));
        double l1=ab*1.0/(k1+1.0), l2=ab*1.0/(k1-1.0);
        double r1=(l2+l1)/2.0;
        double xab=(x[0]-x[1])*1.0/ab, yab=(y[0]-y[1])*1.0/ab, zab=(z[0]-z[1])*1.0/ab;
        double cax=x[0]+xab*(r1-l1), cay=y[0]+yab*(r1-l1), caz=z[0]+zab*(r1-l1);
        double cd=sqrt((x[2]-x[3])*(x[2]-x[3])+(y[2]-y[3])*(y[2]-y[3])+(z[2]-z[3])*(z[2]-z[3]));
        l1=cd*1.0/(k2+1.0);
        l2=cd*1.0/(k2-1.0);
        double r2=(l2+l1)/2.0;
        double xcd=(x[2]-x[3])*1.0/cd, ycd=(y[2]-y[3])*1.0/cd, zcd=(z[2]-z[3])*1.0/cd;
        double cbx=x[2]+xcd*(r2-l1), cby=y[2]+ycd*(r2-l1), cbz=z[2]+zcd*(r2-l1);

        double ans=0;
        double xa,ya,za,ra,va;
        double xb,yb,zb,rb,vb;
        xa=cax; ya=cay; za=caz; ra=r1;
        xb=cbx; yb=cby; zb=cbz; rb=r2;
 
        //printf("%f %f %f %f\n",xa,ya,za,ra);
        //printf("%f %f %f %f\n",xb,yb,zb,rb);
 
 
        double d=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb)+(za-zb)*(za-zb));
        va=(4.0/3.0)*pi*(ra*ra*ra);
        vb=(4.0/3.0)*pi*(rb*rb*rb);
 
        if(d>=ra+rb)
        {
            ans=0;
        }
        else if(d+min(ra,rb)<=max(ra,rb))
        {
            ans=min(va,vb);
        }
        else
        {
            double ka,kb,vva,vvb;
            ka=ra-(((ra*ra)-(rb*rb)+(d*d))/(2*d));
            kb=rb-(((rb*rb)-(ra*ra)+(d*d))/(2*d));
            vva=(pi*ka*ka*(3*ra-ka))/3.0;
            vvb=(pi*kb*kb*(3*rb-kb))/3.0;
            ans=vva+vvb;
        }
        printf("%.10f\n",ans);
    }
    return 0;
}
           

G（DP）

題意：給定n個區間，需要将區間分為k組，每一個組内所有區間取交集，将每個組得到的長度取和，讓這個和最大，輸出這個值

解析：