暴力。求飞行距离以及在海上飞的距离占总距离的百分比。
对于圆心在原点的球，求两个圆弧的交点。可以先弄出两个圆弧所在的平面的法向量，做叉积，求出来的就是两个平面相交的直线的方向向量。因为球面上两个圆弧所在平面相交，交的直线肯定是经过原点的直径所在的直线，所以直径化成单位向量R，就是交点。
z判断交点p在不在圆弧(p1, p2)上，只需要满足 dis(p, p1) + dis(p, p2) == dis(p1, p2)
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define M 1000010
#define ULL unsigned long long
#define LL long long
#define ls (i << 1)
#define rs (ls | 1)
#define md ((ll + rr) >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs
#define inf 0x3f3f3f3f
#define eps 1e-10
#define pii pair<int, int>
#define MP make_pair
#define mod 1000000007
#define sqr(x) ((x) * (x))
#define Pi acos(-1.0)
double dcmp(double x){
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct point{
double x, y, z;
point(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
point operator - (const point &b) const {
return point(x - b.x, y - b.y, z - b.z);
}
point operator * (const double &k) const {
return point(x * k, y * k, z * k);
}
double len(){
return sqrt(x * x + y * y + z * z);
}
point fix(){
double l = len();
return point(x / l, y / l, z / l);
}
};
double torad(double deg){
return deg / 180 * Pi;
}
point get_coord(double lat, double lng, double r){
point ret;
lat = torad(lat), lng = torad(lng);
ret.x = r * cos(lat) * cos(lng);
ret.y = r * cos(lat) * sin(lng);
ret.z = r * sin(lat);
return ret;
}
point cross(point a, point b){
return point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
}
double calc(point a, point b, double R){
double d = (a - b).len();
return 2 * R * asin(d / (2 * R));
}
const double R = 6370.0;
bool check(point p1, point p2, point p){
double len1 = calc(p1, p, R);
double len2 = calc(p2, p, R);
double len = calc(p1, p2, R);
return dcmp(len - len1 - len2) == 0;
}
bool inter(point p1, point p2, point q1, point q2, point &res){
point n1 = cross(p1, p2);
point n2 = cross(q1, q2);
point v1 = cross(n1, n2), v2 = point(0, 0, 0) - v1;
v1 = v1.fix() * R, v2 = v2.fix() * R;
if(check(p1, p2, v1) && check(q1, q2, v1)){ res = v1; return 1; }
if(check(p1, p2, v2) && check(q1, q2, v2)){ res = v2; return 1; }
return 0;
}
point p[33][33], pp[33], fp[133];
point o;
int sz[N];
bool cmp(point a, point b){
return calc(a, o, R) < calc(b, o, R);
}
int main(){
int n, m;
while(scanf("%d", &n) != EOF){
for(int i = 0; i < n; ++i){
scanf("%d", &sz[i]);
for(int j = 0; j < sz[i]; ++j){
double x, y;
scanf("%lf%lf", &x, &y);
p[i][j] = get_coord(x, y, R);
}
p[i][sz[i]] = p[i][0];
}
double ans = 0, sea = 0;
bool f = 0;
scanf("%d", &m);
for(int i = 0; i < m; ++i){
double x, y;
scanf("%lf%lf", &x, &y);
pp[i] = get_coord(x, y, R);
}
for(int i = 1; i < m; ++i){
ans += calc(pp[i], pp[i-1], R);
int cnt = 0;
for(int j = 0; j < n; ++j){
for(int k = 0; k < sz[j]; ++k){
point res;
if(inter(pp[i], pp[i-1], p[j][k], p[j][k+1], res))
fp[cnt++] = res;
}
}
fp[cnt++] = pp[i];
fp[cnt++] = pp[i-1];
o = pp[i-1];
sort(fp, fp + cnt, cmp);
cout << cnt << endl;
for(int i = 1; i < cnt; i += 2){
if(f) sea += calc(fp[i], fp[i-1], R);
else if(i + 1 < cnt)
sea += calc(fp[i+1], fp[i], R);
else ;
}
if(cnt % 2) f ^= 1;
}
printf("%.9f %.9f\n", ans, sea * 100 / ans);
}
return 0;
}