题解

2 条题解

  • 1
    @ 2023-07-30 16:50:39
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<map>
    #include<cctype>
    #include<cmath>
    #include<bitset>
    #include<ctime>
    #define pprint(x) ::print(x),putchar(' ')
    #define fprint(x) ::print(x),putchar('\n')
    using namespace std;
    //#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
    char BB[1 << 15],*SS = BB,*TT = BB;
    using namespace std;
    inline int read()
    {
    int x = 0,f = 1;
    char ch = getchar();
    for(;!isdigit(ch);ch = getchar())
    if(ch == '-')
    f = -1;
    for(;isdigit(ch);ch = getchar())
    x = x * 10 + (ch ^ 48);
    return x * f;
    }
    void print(long long x)
    {
    if(x < 0)
    putchar('-'),x = -x;
    if(x > 9)
    print(x / 10);
    putchar(x % 10 + '0');
    }
    const double pi = acos(-1),eps = 1e-8;
    const int N = 110;
    int dcmp(double x)
    {
    return x < -eps ? -1 : (x > eps);
    }
    struct point
    {
    double x,y,z;
    
    void read()
    {
    scanf("%lf %lf %lf",&x,&y,&z);
    }
    point(double _x = 0,double _y = 0,double _z = 0)
    {
    x = _x,y = _y,z = _z;
    }
    friend point operator + (point szq,point yqy)
    {
    return point(szq.x + yqy.x,szq.y + yqy.y,szq.z + yqy.z);
    }
    friend point operator - (point szq,point yqy)
    {
    return point(szq.x - yqy.x,szq.y - yqy.y,szq.z - yqy.z);
    }
    friend point operator * (point szq,double yqy)
    {
    return point(szq.x * yqy,szq.y * yqy,szq.z * yqy);
    }
    friend double operator * (point szq,point yqy)
    {
    return szq.x * yqy.x + szq.y * yqy.y + szq.z * yqy.z;
    }
    friend point operator / (point szq,double yqy)
    {
    return point(szq.x / yqy,szq.y / yqy,szq.z / yqy);
    }
    friend point operator & (point szq,point yqy)
    {
    return point(szq.y * yqy.z - szq.z * yqy.y,szq.z * yqy.x - szq.x * yqy.z,szq.x * yqy.y - szq.y * yqy.x);
    }
    double lenth()
    {
    return sqrt((*this) * (*this));
    }
    };
    double angle(point a1,point a2,point b1,point b2)
    {
    point p = a2 & a1,q = b2 & b1;
    return acos((p * q) / p.lenth() / q.lenth());
    }
    int n,m;
    point p[N],G;
    int d[N],f[N][N];
    int main()
    {
    n = read(),m = read();
    for(int i = 1;i <= n;i++)
    p[i].read();
    for(int i = 1;i <= m;i++)
    {
    d[i] = read();
    for(int j = 1;j <= d[i];j++)
    f[i][j] = read();
    }
    point u = p[1];
    double sum = 0;
    for(int i = 1;i <= m;i++)
    {
    point a = p[f[i][1]],b,c;
    for(int j = 2;j < d[i];j++)
    {
    b = p[f[i][j]],c = p[f[i][j + 1]];
    double w = fabs(((b - a) & (c - a)) * (u - a));
    G = G + (u + a + b + c) * w * 0.25,sum += w;
    }
    }
    G = G / sum;
    for(int i = 1;i <= n;i++)
    p[i] = p[i] - G;
    double all = 4 * pi;
    for(int i = 1;i <= m;i++)
    {
    double sum = 0;
    f[i][0] = f[i][d[i]],f[i][d[i] + 1] = f[i][1];
    for(int j = 1;j <= d[i];j++)
    sum += angle(p[f[i][j]],p[f[i][j - 1]],p[f[i][j]],p[f[i][j + 1]]);
    sum -= (d[i] - 2) * pi;
    printf("%.7lf\n",sum / all);
    }
    return 0;
    }
    
    
  • 1
    @ 2020-04-30 17:12:02

    重心的求法没什么好说的。

    对于一个多边形,区域 T 是多边形以重心为点光源,在单位球上的投影,该投影是一个曲面多边形。

    考虑该曲面多边形的求法,设边数为 d,我们将这个曲面多边形“三角剖分”,那么它的面积就等于所有曲面三角形的面积之和。题目中给出了 \operatorname{Area}(ABC)=\alpha +\beta+\gamma-\piArea(ABC)=α+β+γ−π,所以总面积 S=S= 所有三角形内角和 -(d-2)\pi−(d−2)π,d-2d−2 为三角形个数。

    曲面三角形的内角和之和等于曲面多边形内角和,对于曲面多边形一个内角,它等于重心与原多边形一对邻边形成的两个平面的夹角。

    最后概率等于区域 T 的面积除以单位球的表面积。

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<map>
    #include<cctype>
    #include<cmath>
    #include<bitset>
    #include<ctime>
    #define pprint(x) ::print(x),putchar(' ')
    #define fprint(x) ::print(x),putchar('\n')
    using namespace std;
    //#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
    char BB[1 << 15],*SS = BB,*TT = BB;
    using namespace std;
    inline int read()
    {
    int x = 0,f = 1;
    char ch = getchar();
    for(;!isdigit(ch);ch = getchar())
    if(ch == '-')
    f = -1;
    for(;isdigit(ch);ch = getchar())
    x = x * 10 + (ch ^ 48);
    return x * f;
    }
    void print(long long x)
    {
    if(x < 0)
    putchar('-'),x = -x;
    if(x > 9)
    print(x / 10);
    putchar(x % 10 + '0');
    }
    const double pi = acos(-1),eps = 1e-8;
    const int N = 110;
    int dcmp(double x)
    {
    return x < -eps ? -1 : (x > eps);
    }
    struct point
    {
    double x,y,z;

    void read()
    {
    scanf("%lf %lf %lf",&x,&y,&z);
    }
    point(double _x = 0,double _y = 0,double _z = 0)
    {
    x = _x,y = _y,z = _z;
    }
    friend point operator + (point szq,point yqy)
    {
    return point(szq.x + yqy.x,szq.y + yqy.y,szq.z + yqy.z);
    }
    friend point operator - (point szq,point yqy)
    {
    return point(szq.x - yqy.x,szq.y - yqy.y,szq.z - yqy.z);
    }
    friend point operator * (point szq,double yqy)
    {
    return point(szq.x * yqy,szq.y * yqy,szq.z * yqy);
    }
    friend double operator * (point szq,point yqy)
    {
    return szq.x * yqy.x + szq.y * yqy.y + szq.z * yqy.z;
    }
    friend point operator / (point szq,double yqy)
    {
    return point(szq.x / yqy,szq.y / yqy,szq.z / yqy);
    }
    friend point operator & (point szq,point yqy)
    {
    return point(szq.y * yqy.z - szq.z * yqy.y,szq.z * yqy.x - szq.x * yqy.z,szq.x * yqy.y - szq.y * yqy.x);
    }
    double lenth()
    {
    return sqrt((*this) * (*this));
    }
    };
    double angle(point a1,point a2,point b1,point b2)
    {
    point p = a2 & a1,q = b2 & b1;
    return acos((p * q) / p.lenth() / q.lenth());
    }
    int n,m;
    point p[N],G;
    int d[N],f[N][N];
    int main()
    {
    n = read(),m = read();
    for(int i = 1;i <= n;i++)
    p[i].read();
    for(int i = 1;i <= m;i++)
    {
    d[i] = read();
    for(int j = 1;j <= d[i];j++)
    f[i][j] = read();
    }
    point u = p[1];
    double sum = 0;
    for(int i = 1;i <= m;i++)
    {
    point a = p[f[i][1]],b,c;
    for(int j = 2;j < d[i];j++)
    {
    b = p[f[i][j]],c = p[f[i][j + 1]];
    double w = fabs(((b - a) & (c - a)) * (u - a));
    G = G + (u + a + b + c) * w * 0.25,sum += w;
    }
    }
    G = G / sum;
    for(int i = 1;i <= n;i++)
    p[i] = p[i] - G;
    double all = 4 * pi;
    for(int i = 1;i <= m;i++)
    {
    double sum = 0;
    f[i][0] = f[i][d[i]],f[i][d[i] + 1] = f[i][1];
    for(int j = 1;j <= d[i];j++)
    sum += angle(p[f[i][j]],p[f[i][j - 1]],p[f[i][j]],p[f[i][j + 1]]);
    sum -= (d[i] - 2) * pi;
    printf("%.7lf\n",sum / all);
    }
    return 0;
    }

  • 1

信息

ID
1998
难度
3
分类
(无)
标签
递交数
56
已通过
27
通过率
48%
被复制
2
上传者