BZOJ 4603 平凡的骰子

Link

省选的时候连题意都没读懂的题。。 # Solution 按照要求模拟即可 1. 混合积 三个向量的混合积是以它们为棱的平行六面体的有向体积。 \((\overrightarrow l\times\overrightarrow m)\cdot \overrightarrow k=S(\overrightarrow n\cdot \overrightarrow k)=Sh=V\),\(\overrightarrow n\)为单位向量 2. 多面体重心 先考虑多边形重心。首先,三形的重心是三个点相加\(/3\)。把多边形分成很多个互不相交的三角形,分别求出它们的重心,多边形的重心\(G=\dfrac {\sum G\_iS\_i}S\) 多面体的重心也相似,只是把多面体剖成四面体,四面体的重心就是四点座标相加\(/4\)。把上式的\(S\)换成\(V\),即可。 3. 二面角 数学老师讲课的时候说二面角的是锐角还是钝角只能自己感受,我是拒绝的。思考了很长时间,我终于找到了可以形式化的求法:用右手定则可以判断叉积的方向,让两个向量叉积朝向同侧(内/外),然后再用反余弦,再用\(180^{\circ}\)减即可。(一眼秒掉这个做法的大神请不要D我。。)

然后这个题就可做了。。Orz考场A掉这道题的zff。。 # Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100+10;
using std::vector;
typedef double ld;
const ld eps=1e-5,pi=acos(-1.0);
int fcmp(ld x)
{
if(-eps<x && x<eps) return 0;
return x<0?-1:1;
}
template <class T> T abs(T x){return x<0?-x:x;}
struct vec
{
ld x,y,z;
vec(){x=y=z=0;}
vec(ld _x,ld _y,ld _z):x(_x),y(_y),z(_z){}
ld norm(){return sqrt(x*x+y*y+z*z);}
vec& operator +=(vec a){x+=a.x,y+=a.y,z+=a.z;return *this;}
vec& operator -=(vec a){x-=a.x,y-=a.y,z-=a.z;return *this;}
vec& operator *=(ld t){x*=t,y*=t,z*=t;return *this;}
vec& operator /=(ld t){x/=t,y/=t,z/=t;return *this;}
};
typedef vec point;
//二维向量z座标为0,所以含有z的维都为零,只剩下一维,就成了叉积的模。
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y,a.z+b.z);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y,a.z-b.z);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t,a.z*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t,a.z/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y+a.z*b.z;}
vec outer(vec a,vec b){return vec(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
point plane[MAXN][MAXN],p[MAXN],gc;int pac[MAXN],n,fn;
point GC(point a,point b,point c,point d){return (a+b+c+d)/4;}
ld volume(point a,point b,point c,point d){return abs(inner(outer(b-a,c-a),d-a))/6;}
point GC()
{
point O,C;
for(int i=1;i<=n;i++)
O+=p[i];
O/=n;
ld v=0;
for(int i=1;i<=fn;i++)
{
point *sur=plane[i];
for(int j=2;j<=pac[i]-1;j++)
{
ld subv=volume(sur[1],sur[j],sur[j+1],O);
C+=GC(sur[1],sur[j],sur[j+1],O)*subv;
v+=subv;
}
}
C/=v;
return C;
}
ld dihe(point l,point m1,point m2,point r)
{
vec lv=l-m2,mv=m1-m2,rv=r-m2;
vec n1=outer(mv,rv),n2=outer(lv,mv);
ld cosine=inner(n1,n2)/(n1.norm()*n2.norm());
return pi-acos(cosine);
}
ld area(int x)
{
ld res=0;point *sur=plane[x];
for(int i=2;i<=pac[x]-1;i++)
res+=dihe(sur[i+1], sur[1],gc, sur[i])+
dihe(sur[1], sur[i],gc, sur[i+1])+
dihe(sur[i], sur[i+1],gc, sur[1])-pi;
return res;
}
int main()
{
//freopen("input","r",stdin);
red(n),red(fn);
for(int i=1;i<=n;i++)
fred(p[i].x),fred(p[i].y),fred(p[i].z);
for(int i=1;i<=fn;i++)
{
int t;red(pac[i]);
for(int j=1;j<=pac[i];j++)
red(t),plane[i][j]=p[t];
}
gc=GC();
for(int i=1;i<=fn;i++)
printf("%.7lf\n",area(i)/(4*pi));
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利