C++14(g++5.4) 解法, 执行用时: 155ms, 内存消耗: 7372K, 提交时间: 2020-01-08 15:18:37
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100011;
const int mod = 1e9 + 7;
typedef double D;
D pi = acos((D)-1.);
typedef long long J;
struct P {
LL x, y, z;
void scan() {
cin >> x >> y >> z;
}
void print() const {
cerr << x << ' ' << y << ' ' << z << endl;
}
P operator + (const P & b) const { return P{x + b.x, y + b.y, z + b.z}; }
P operator - (const P & b) const { return P{x - b.x, y - b.y, z - b.z}; }
P operator * (const P & b) const { return P{y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x}; }
J operator % (const P & b) const { return (J)x * b.x + (J)y * b.y + (J)z * b.z; }
LL sqrlen() const { return x * x + y * y + z * z; }
D len() const { return sqrt((D)x * x + (D)y * y + (D)z * z); }
bool operator < (const P & b) const {
return x < b.x || x == b.x && y < b.y || x == b.x && y == b.y && z < b.z;
}
int sgn() const {
return *this < P{0, 0, 0} ? -1 : P{0, 0, 0} < *this ? 1 : 0;
}
bool operator == (const P & b) const { return x == b.x && y == b.y && z == b.z; }
} a[N], b[N], c[N];
int main() {
int n;
scanf("%d", &n);
for(int i(0); i < n; i++) {
a[i].scan();
}
int mxk, mxj, cnt;
for(int d = 0; d < 2; d++) {
int nb = 0;
for(int i(1); i < n; i++) {
b[nb++] = a[i];
if(a[0] * a[i] == P{0, 0, 0}) {
nb--;
}
}
P norm = a[0] * P{1, 0, 0};
if(norm == P{0, 0, 0}) norm = a[0] * P{0, 1, 0};
P n1 = a[0] * norm;
sort(b, b + nb, [&](const P & x, const P & y) {
LL d1 = x % norm < 0 || x % norm == 0 && x % n1 < 0;
LL d2 = y % norm < 0 || y % norm == 0 && y % n1 < 0;
if(d1 == d2) {
return (x * y % a[0]) > 0 || (x * y % a[0] == 0) && x % a[0] > y % a[0];
}else return d1 < d2;
});
cnt = 0;
mxj = -1; mxk = -1;
for(int i(0); i < nb; i++) {
if(i == 0 || b[i] * b[i - 1] % a[0] != 0) cnt++;
}
if(cnt >= 2) {
for(int i(0); i < nb; i++) {
LL res = b[i] * b[(i + 1) % nb] % a[0];
if(res < 0 || res == 0 && (b[i] * a[0]).sgn() != (b[(i + 1) % nb] * a[0]).sgn()) {
mxj = i;
}
}
}else mxj = 0;
if(mxj == -1 && d == 0) {
vector<P> v;
for(int i(0); i < nb; i++) {
while(v.size() >= 2u && (v[v.size() - 2] * v.back() % b[i] <= 0)) {
v.pop_back();
}
v.push_back(b[i]);
}
int op = 0, ed = (int)v.size();
for(;;) {
if(ed - op >= 3 && (v[ed - 2] * v[ed - 1] % v[op] <= 0)) {
ed--;
continue;
}else if(ed - op >= 3 && (v[ed - 1] * v[op] % v[op + 1] <= 0)) {
op++;
continue;
}else break;
}
for(int i(0); i < n; i++) if(a[i] == v[op]) {
swap(a[i], a[0]);
}
continue;
}
if(mxj == -1) {
printf("0\n");
exit(0);
}
for(int i(1); i < n; i++) if(a[i] == b[mxj]) { swap(a[i], a[1]); break; }
}
P dir = a[0] + a[1];
int nc = 0;
for(int i = 0; i < n; i++) {
if(a[0] * a[1] % a[i] == 0) {
c[nc++] = a[i];
}
}
if(nc == n) {
printf("1\n");
exit(0);
}
sort(c, c+ nc, [&](const P & x, const P & y) {
int d1 = x.sgn(), d2 = y.sgn();
if(d1 == d2) {
return (x * y).sgn() > 0;
}else return d1 < d2;
});
cnt = 0; mxj = -1;
bool full_hemi = true;
for(int i(0); i < nc; i++) {
LL res = (c[i] * c[(i + 1) % nc]).sgn();
if(res <= 0) {
mxj = i;
mxk = (i + 1) % nc;
full_hemi = false;
break;
}
}
if(full_hemi) {
printf("0.5\n");
exit(0);
}
for(int i(0); i < n; i++) {
if(a[i] == c[mxj]) {
swap(a[0], a[i]);
break;
}
}
for(int i(0); i < n; i++) {
if(a[i] == c[mxk]) {
swap(a[1], a[i]);
break;
}
}
//a[0].print();
//a[1].print();
if((a[0] * a[1]).sgn() == 0) {
sort(a + 2, a + n, [&](const P & x, const P & y) {
return (x * y % a[0]) < 0;
});
D ans = 0;
for(int i(2); i + 1 < n; i++) {
//a[i].print();
//a[i + 1].print();
ans += asin(abs((a[i] * a[0]) % (a[i + 1])) / abs((a[i] * a[0]).len()) / a[i + 1].len());
}
printf("%.12f\n", 1 - ans / 2 / pi);
exit(0);
}
for(int i(2); i < n; i++) {
if(a[0] * a[1] % a[i] == 0) {
swap(a[i], a[n - 1]);
n--; i--;
}
}
sort(a + 2, a + n, [&](const P & x, const P & y) {
return x * y % dir > 0;
});
if(a[0] * a[2] % dir > 0) {
}else {
swap(a[0], a[1]);
}
for(int i(1); i + 1 < n; i++) swap(a[i], a[i + 1]);
vector<P> vec;
for(int i(0); i < n; i++) {
while(vec.size() >= 2u && (vec[vec.size() - 2] * vec.back() % a[i] <= 0)) {
vec.pop_back();
}
vec.push_back(a[i]);
}
int nv = vec.size();
double ans = 0;
for(int i(1); i + 1 < nv; i++) {
P x = vec[i];
P y = vec[(i + 1) % nv];
P z = vec[0];
D lx = x.len(), ly = y.len(), lz = z.len();
D tmp = atan(abs(x * y % z) / (lx * ly * lz + lx * (y % z) + ly * (x % z) + lz * (x % y)));
if(tmp < 0) tmp += pi;
ans += tmp * 2;
}
printf("%.12f\n", 1 - ans / 4 / pi);
}
C++(clang++11) 解法, 执行用时: 179ms, 内存消耗: 7440K, 提交时间: 2021-04-10 12:02:49
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100011;
const int mod = 1e9 + 7;
typedef double D;
D pi = acos((D)-1.);
typedef long long J;
struct P {
LL x, y, z;
void scan() {
cin >> x >> y >> z;
}
void print() const {
cerr << x << ' ' << y << ' ' << z << endl;
}
P operator + (const P & b) const { return P{x + b.x, y + b.y, z + b.z}; }
P operator - (const P & b) const { return P{x - b.x, y - b.y, z - b.z}; }
P operator * (const P & b) const { return P{y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x}; }
J operator % (const P & b) const { return (J)x * b.x + (J)y * b.y + (J)z * b.z; }
LL sqrlen() const { return x * x + y * y + z * z; }
D len() const { return sqrt((D)x * x + (D)y * y + (D)z * z); }
bool operator < (const P & b) const {
return x < b.x || x == b.x && y < b.y || x == b.x && y == b.y && z < b.z;
}
int sgn() const {
return *this < P{0, 0, 0} ? -1 : P{0, 0, 0} < *this ? 1 : 0;
}
bool operator == (const P & b) const { return x == b.x && y == b.y && z == b.z; }
} a[N], b[N], c[N];
int main() {
int n;
scanf("%d", &n);
for(int i(0); i < n; i++) {
a[i].scan();
}
int mxk, mxj, cnt;
for(int d = 0; d < 2; d++) {
int nb = 0;
for(int i(1); i < n; i++) {
b[nb++] = a[i];
if(a[0] * a[i] == P{0, 0, 0}) {
nb--;
}
}
P norm = a[0] * P{1, 0, 0};
if(norm == P{0, 0, 0}) norm = a[0] * P{0, 1, 0};
P n1 = a[0] * norm;
sort(b, b + nb, [&](const P & x, const P & y) {
LL d1 = x % norm < 0 || x % norm == 0 && x % n1 < 0;
LL d2 = y % norm < 0 || y % norm == 0 && y % n1 < 0;
if(d1 == d2) {
return (x * y % a[0]) > 0 || (x * y % a[0] == 0) && x % a[0] > y % a[0];
}else return d1 < d2;
});
cnt = 0;
mxj = -1; mxk = -1;
for(int i(0); i < nb; i++) {
if(i == 0 || b[i] * b[i - 1] % a[0] != 0) cnt++;
}
if(cnt >= 2) {
for(int i(0); i < nb; i++) {
LL res = b[i] * b[(i + 1) % nb] % a[0];
if(res < 0 || res == 0 && (b[i] * a[0]).sgn() != (b[(i + 1) % nb] * a[0]).sgn()) {
mxj = i;
}
}
}else mxj = 0;
if(mxj == -1 && d == 0) {
vector<P> v;
for(int i(0); i < nb; i++) {
while(v.size() >= 2u && (v[v.size() - 2] * v.back() % b[i] <= 0)) {
v.pop_back();
}
v.push_back(b[i]);
}
int op = 0, ed = (int)v.size();
for(;;) {
if(ed - op >= 3 && (v[ed - 2] * v[ed - 1] % v[op] <= 0)) {
ed--;
continue;
}else if(ed - op >= 3 && (v[ed - 1] * v[op] % v[op + 1] <= 0)) {
op++;
continue;
}else break;
}
for(int i(0); i < n; i++) if(a[i] == v[op]) {
swap(a[i], a[0]);
}
continue;
}
if(mxj == -1) {
printf("0\n");
exit(0);
}
for(int i(1); i < n; i++) if(a[i] == b[mxj]) { swap(a[i], a[1]); break; }
}
P dir = a[0] + a[1];
int nc = 0;
for(int i = 0; i < n; i++) {
if(a[0] * a[1] % a[i] == 0) {
c[nc++] = a[i];
}
}
if(nc == n) {
printf("1\n");
exit(0);
}
sort(c, c+ nc, [&](const P & x, const P & y) {
int d1 = x.sgn(), d2 = y.sgn();
if(d1 == d2) {
return (x * y).sgn() > 0;
}else return d1 < d2;
});
cnt = 0; mxj = -1;
bool full_hemi = true;
for(int i(0); i < nc; i++) {
LL res = (c[i] * c[(i + 1) % nc]).sgn();
if(res <= 0) {
mxj = i;
mxk = (i + 1) % nc;
full_hemi = false;
break;
}
}
if(full_hemi) {
printf("0.5\n");
exit(0);
}
for(int i(0); i < n; i++) {
if(a[i] == c[mxj]) {
swap(a[0], a[i]);
break;
}
}
for(int i(0); i < n; i++) {
if(a[i] == c[mxk]) {
swap(a[1], a[i]);
break;
}
}
//a[0].print();
//a[1].print();
if((a[0] * a[1]).sgn() == 0) {
sort(a + 2, a + n, [&](const P & x, const P & y) {
return (x * y % a[0]) < 0;
});
D ans = 0;
for(int i(2); i + 1 < n; i++) {
//a[i].print();
//a[i + 1].print();
ans += asin(abs((a[i] * a[0]) % (a[i + 1])) / abs((a[i] * a[0]).len()) / a[i + 1].len());
}
printf("%.10f\n", 1 - ans / 2 / pi);
exit(0);
}
for(int i(2); i < n; i++) {
if(a[0] * a[1] % a[i] == 0) {
swap(a[i], a[n - 1]);
n--; i--;
}
}
sort(a + 2, a + n, [&](const P & x, const P & y) {
return x * y % dir > 0;
});
if(a[0] * a[2] % dir > 0) {
}else {
swap(a[0], a[1]);
}
for(int i(1); i + 1 < n; i++) swap(a[i], a[i + 1]);
vector<P> vec;
for(int i(0); i < n; i++) {
while(vec.size() >= 2u && (vec[vec.size() - 2] * vec.back() % a[i] <= 0)) {
vec.pop_back();
}
vec.push_back(a[i]);
}
int nv = vec.size();
double ans = 0;
for(int i(1); i + 1 < nv; i++) {
P x = vec[i];
P y = vec[(i + 1) % nv];
P z = vec[0];
D lx = x.len(), ly = y.len(), lz = z.len();
D tmp = atan(abs(x * y % z) / (lx * ly * lz + lx * (y % z) + ly * (x % z) + lz * (x % y)));
if(tmp < 0) tmp += pi;
ans += tmp * 2;
}
printf("%.9f\n", 1 - ans / 4 / pi);
}
be a sphere with radius 
and center %7D)
. Let 
be 
points on the surface of 
are fixed while the position of 
is a uniform random point on the surface of 
be 
and 
otherwise. Calculate the expected value of denoting the number of points (
).
-th line of the next
denoting the point
(
).
It is guaranteed that.