fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5. using namespace std;
  6. typedef long double ld;
  7.  
  8. struct vec3{
  9.     ld x,y,z;
  10.     vec3 operator-(vec3 const &a)const{return {x-a.x,y-a.y,z-a.z};}
  11.     void fix(){ld l=hypotl(hypotl(x,y),z); x/=l,y/=l,z/=l;}
  12.     ld dot(vec3 const &b)const{return x*b.x+y*b.y+z*b.z;}
  13.     vec3 cross(vec3 const &b)const{return {y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x};}
  14. };
  15.  
  16. vector<vec3> path(bool loop=false){
  17.     int n; cin>>n;
  18.     vector<vec3> res(n);
  19.     for (auto &i: res){
  20.         ld lon,lat; cin>>lat>>lon;
  21.         lon*=M_PI/180.L, lat*=M_PI/180.L;
  22.         i={cos(lat)*sin(lon), sin(lat), cos(lat)*cos(lon)};
  23.     }
  24.     if (loop) res.push_back(res.front());
  25.     return res;
  26. }
  27.  
  28. vector<vector<vec3>> continents(){
  29.     int n; cin>>n;
  30.     vector<vector<vec3>> res(n);
  31.     for (auto &i: res) i=path(true);
  32.     return res;
  33. }
  34.  
  35. vector<double> find_intersections(vec3 a, vec3 b, vector<vec3> const &loop){
  36.     static vector<double> res;
  37.     res.clear();
  38.  
  39.     for (int i=1; i<loop.size(); i++){
  40.         vec3 e=loop[i-1],f=loop[i];
  41.  
  42.         vec3 u=(e-f).cross(e); u.fix();
  43.         vec3 v=(b-a).cross(b); v.fix();
  44.         vec3 w=u.cross(v); w.fix();
  45.         if (w.dot(a)+w.dot(b)<0) w={-w.x,-w.y,-w.z};
  46.  
  47.         if (abs(acosl(w.dot(a))+acosl(w.dot(b))-acosl(a.dot(b)))
  48.            +abs(acosl(w.dot(e))+acosl(w.dot(f))-acosl(e.dot(f))) < 1e-9L)
  49.             res.push_back(acosl(w.dot(a)));
  50.     }
  51.     return res;
  52. }
  53.  
  54. int main(){
  55.     auto c=continents();
  56.     auto p=path();
  57.  
  58.     vector<ld> when;
  59.     ld len=0.L,frac=0.L;
  60.     for (int i=1; i<p.size(); i++){
  61.         for (auto const &con: c)
  62.             for (auto const f: find_intersections(p[i-1],p[i],con))
  63.                 when.push_back(len+f);
  64.         len+=acosl(p[i].dot(p[i-1]));
  65.     }
  66.     sort(when.begin(),when.end());
  67.     for (int i=0; i+2<=when.size(); i+=2) frac+=when[i+1]-when[i];
  68.     frac/=len;
  69.  
  70.     cout.precision(10);
  71.     cout<<fixed<<len*6370<<" "<<frac*100<<endl;
  72. }
  73.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
1
4 -45 0 45 0 45 90 -45 90
5 0 180 0 359 0 160 0 170 0 180
stdout
copy 
40023.8904067340 25.0000000000
https://ideone.com/5MWM5R
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!