API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 14th, 2021
404
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.67 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<class T>
  5. struct point{
  6.     T x{}, y{};
  7.     point(){ }
  8.     template<class U> point(const point<U> &otr): x(otr.x), y(otr.y){ }
  9.     template<class U, class V> point(U x, V y): x(x), y(y){ }
  10.     template<class U> explicit operator point<U>() const{
  11.         return point<U>(static_cast<U>(x), static_cast<U>(y));
  12.     }
  13.     T operator*(const point &otr) const{
  14.         return x * otr.x + y * otr.y;
  15.     }
  16.     T operator^(const point &otr) const{
  17.         return x * otr.y - y * otr.x;
  18.     }
  19.     point operator+(const point &otr) const{
  20.         return {x + otr.x, y + otr.y};
  21.     }
  22.     point &operator+=(const point &otr){
  23.         return *this = *this + otr;
  24.     }
  25.     point operator-(const point &otr) const{
  26.         return {x - otr.x, y - otr.y};
  27.     }
  28.     point &operator-=(const point &otr){
  29.         return *this = *this - otr;
  30.     }
  31.     point operator-() const{
  32.         return {-x, -y};
  33.     }
  34. #define scalarop_l(op) friend point operator op(const T &c, const point &p){ return {c op p.x, c op p.y}; }
  35.     scalarop_l(+) scalarop_l(-) scalarop_l(*) scalarop_l(/)
  36. #define scalarop_r(op) point operator op(const T &c) const{ return {x op c, y op c}; }
  37.     scalarop_r(+) scalarop_r(-) scalarop_r(*) scalarop_r(/)
  38. #define scalarapply(op) point &operator op(const T &c){ return *this = *this op c; }
  39.     scalarapply(+=) scalarapply(-=) scalarapply(*=) scalarapply(/=)
  40. #define compareop(op) bool operator op(const point &otr) const{ return tie(x, y) op tie(otr.x, otr.y); }
  41.     compareop(>) compareop(<) compareop(>=) compareop(<=) compareop(==) compareop(!=)
  42. #undef scalarop_l
  43. #undef scalarop_r
  44. #undef scalarapply
  45. #undef compareop
  46.     double norm() const{
  47.         return sqrt(x * x + y * y);
  48.     }
  49.     T squared_norm() const{
  50.         return x * x + y * y;
  51.     }
  52.     double angle() const{
  53.         return atan2(y, x);
  54.     } // [-pi, pi]
  55.     point<double> unit() const{
  56.         return point<double>(x, y) / norm();
  57.     }
  58.     point perp() const{
  59.         return {-y, x};
  60.     }
  61.     point<double> normal() const{
  62.         return perp().unit();
  63.     }
  64.     point<double> rotate(const double &theta) const{
  65.         return {x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)};
  66.     }
  67.     point reflect_x() const{
  68.         return {x, -y};
  69.     }
  70.     point reflect_y() const{
  71.         return {-x, y};
  72.     }
  73.     point reflect(const point &o = {}) const{
  74.         return {2 * o.x - x, 2 * o.y - y};
  75.     }
  76.     bool operator||(const point &otr) const{
  77.         return !(*this ^ otr);
  78.     }
  79. };
  80. template<class T> istream &operator>>(istream &in, point<T> &p){
  81.     return in >> p.x >> p.y;
  82. }
  83. template<class T> ostream &operator<<(ostream &out, const point<T> &p){
  84.     return out << "{" << p.x << ", " << p.y << "}";
  85. }
  86. template<class T>
  87. double distance(const point<T> &p, const point<T> &q){
  88.     return (p - q).norm();
  89. }
  90. template<class T>
  91. T squared_distance(const point<T> &p, const point<T> &q){
  92.     return (p - q).squared_norm();
  93. }
  94. template<class T, class U, class V>
  95. T doubled_signed_area(const point<T> &p, const point<U> &q, const point<V> &r){
  96.     return q - p ^ r - p;
  97. }
  98. template<class T>
  99. T doubled_signed_area(const vector<point<T>> &a){
  100.     assert(!a.empty());
  101.     int n = (int)a.size();
  102.     T res = a.back() ^ a.front();
  103.     for(auto i = 1; i < n; ++ i) res += a[i - 1] ^ a[i];
  104.     return res;
  105. }
  106. template<class T>
  107. double angle(const point<T> &p, const point<T> &q){
  108.     return atan2(p ^ q, p * q);
  109. }
  110. template<class T>
  111. bool is_sorted(const point<T> &origin, point<T> p, point<T> q, point<T> r){
  112.     p -= origin, q -= origin, r -= origin;
  113.     T x = p ^ r, y = p ^ q, z = q ^ r;
  114.     return x >= 0 && y >= 0 && z >= 0 || x < 0 && (y >= 0 || z >= 0);
  115. } // check if p->q->r is sorted with respect to the origin
  116. template<class T, class IT>
  117. bool is_sorted(const point<T> &origin, IT begin, IT end){
  118.     for(auto i = 0; i < (int)(end - begin) - 2; ++ i) if(!is_sorted(origin, *(begin + i), *(begin + i + 1), *(begin + i + 2))) return false;
  119.     return true;
  120. } // check if begin->end is sorted with respect to the origin
  121. template<class T>
  122. bool counterclockwise(const point<T> &p, const point<T> &q, const point<T> &r){
  123.     return doubled_signed_area(p, q, r) > 0;
  124. }
  125. template<class T>
  126. bool clockwise(const point<T> &p, const point<T> &q, const point<T> &r){
  127.     return doubled_signed_area(p, q, r) < 0;
  128. }
  129.  
  130. using pointint = point<int>;
  131. using pointll = point<long long>;
  132. using pointlll = point<__int128_t>;
  133. using pointd = point<double>;
  134. using pointld = point<long double>;
  135.  
  136. // Requires point
  137. template<class T>
  138. struct line{
  139.     point<T> p{}, d{}; // p + d*t
  140.     line(){ }
  141.     line(point<T> p, point<T> q, bool Two_Points = true): p(p), d(Two_Points ? q - p : q){ }
  142.     line(point<T> d): p(), d(static_cast<point<T>>(d)){ }
  143.     line(T a, T b, T c): p(a ? -c / a : 0, !a && b ? -c / b : 0), d(-b, a){ }
  144.     template<class U> explicit operator line<U>() const{
  145.         return line<U>(point<U>(p), point<U>(d), false);
  146.     }
  147.     point<T> q() const{
  148.         return p + d;
  149.     }
  150.     operator bool() const{
  151.         return d.x != 0 || d.y != 0;
  152.     }
  153.     tuple<T, T, T> coef() const{
  154.         return {d.y, -d.x, d.perp() * p};
  155.     } // d.y (X - p.x) - d.x (Y - p.y) = 0
  156.     bool operator||(const line<T> &L) const{
  157.         return d || L.d;
  158.     }
  159.     line translate(T x) const{
  160.         auto dir = d.perp();
  161.         return {p + dir.unit() * x, d, false};
  162.     }
  163. };
  164. template<class T> istream &operator>>(istream &in, line<T> &l){
  165.     in >> l.p >> l.d, l.d -= l.p;
  166.     return in;
  167. }
  168. template<class T> ostream &operator<<(ostream &out, const line<T> &l){
  169.     return out << "{" << l.p << " -> " << l.q() << "}";
  170. }
  171. template<class T>
  172. bool on_line(const point<T> &p, const line<T> &L){
  173.     return L ? p - L.p || L.d : p == L.p;
  174. }
  175. template<class T>
  176. bool on_ray(const point<T> &p, const line<T> &L){
  177.     return L ? (L.p - p || L.q() - p) && (L.p - p) * L.d <= 0 : p == L.p;
  178. }
  179. template<class T>
  180. bool on_segment(const point<T> &p, const line<T> &L){
  181.     return L ? (L.p - p || L.q() - p) && (L.p - p) * (L.q() - p) <= 0 : p == L.p;
  182. }
  183. template<class T>
  184. bool on_open_segment(const point<T> &p, const line<T> &L){
  185.     return L ? (L.p - p || L.q() - p) && (L.p - p) * (L.q() - p) < 0 : p == L.p;
  186. }
  187. template<class T>
  188. double distance_to_line(const point<T> &p, const line<T> &L){
  189.     return L ? abs(p - L.p ^ L.d) / L.d.norm() : distance(p, L.p);
  190. }
  191. template<class T>
  192. double distance_to_ray(const point<T> &p, const line<T> &L){
  193.     return (p - L.p) * L.d <= 0 ? distance(p, L.p) : distance_to_line(p, L);
  194. }
  195. template<class T>
  196. double distance_to_segment(const point<T> &p, const line<T> &L){
  197.     return (p - L.p) * L.d <= 0 ? distance(p, L.p) : (p - L.q()) * L.d >= 0 ? distance(p, L.q()) : distance_to_line(p, L);
  198. }
  199. template<class T>
  200. point<double> projection(const point<T> &p, const line<T> &L){
  201.     return static_cast<point<double>>(L.p) + (L ? (p - L.p) * L.d / L.d.squared_norm() * static_cast<point<double>>(L.d) : point<double>());
  202. }
  203. template<class T>
  204. point<double> reflection(const point<T> &p, const line<T> &L){
  205.     return 2.0 * projection(p, L) - static_cast<point<double>>(p);
  206. }
  207. template<class T>
  208. point<double> closest_point_on_segment(const point<T> &p, const line<T> &L){
  209.     return (p - L.p) * L.d <= 0 ? static_cast<point<double>>(L.p) : ((p - L.q()) * L.d >= 0 ? static_cast<point<double>>(L.q()) : projection(p, L));
  210. }
  211.  
  212. using lineint = line<int>;
  213. using linell = line<long long>;
  214. using linelll = line<__int128_t>;
  215. using lined = line<double>;
  216. using lineld = line<long double>;
  217.  
  218. // Requires point and line
  219. template<int TYPE>
  220. struct EndpointChecker{ };
  221. // For rays
  222. template<>
  223. struct EndpointChecker<0>{
  224.     template<class T>
  225.     bool operator()(const T& a, const T& b) const{
  226.         return true;
  227.     }
  228. };
  229. // For closed end
  230. template<>
  231. struct EndpointChecker<1>{
  232.     template<class T>
  233.     bool operator()(const T& a, const T& b) const{
  234.         return a <= b;
  235.     }
  236. };
  237. // For open end
  238. template<>
  239. struct EndpointChecker<2>{
  240.     template<class T>
  241.     bool operator()(const T& a, const T& b) const{
  242.         return a < b;
  243.     }
  244. };
  245. // Assumes parallel lines do not intersect
  246. template<int LA, int LB, int RA, int RB, class T>
  247. optional<point<double>> intersect_no_parallel_overlap(const line<T> &L, const line<T> &M){
  248.     auto s = L.d ^ M.d;
  249.     if(s == 0) return {};
  250.     auto ls = M.p - L.p ^ M.d, rs = M.p - L.p ^ L.d;
  251.     if(s < 0) s = -s, ls = -ls, rs = -rs;
  252.     if(EndpointChecker<LA>()(decltype(ls)(0), ls) && EndpointChecker<LB>()(ls, s) &&
  253.     EndpointChecker<RA>()(decltype(rs)(0), rs) && EndpointChecker<RB>()(rs, s)){
  254.         return static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d);
  255.     }
  256.     else return {};
  257. }
  258. // Assumes parallel lines do not intersect
  259. template<class T>
  260. optional<point<double>> intersect_closed_segments_no_parallel_overlap(const line<T> &L, const line<T> &M){
  261.     return intersect_no_parallel_overlap<1, 1, 1, 1>(L, M);
  262. }
  263. // Assumes nothing
  264. template<class T>
  265. optional<line<double>> intersect_closed_segments(const line<T> &L, const line<T> &M){
  266.     auto s = L.d ^ M.d, ls = M.p - L.p ^ M.d;
  267.     if(!s){
  268.         if(ls) return {};
  269.         auto Lp = L.p, Lq = L.q(), Mp = M.p, Mq = M.q();
  270.         if(Lp > Lq) swap(Lp, Lq);
  271.         if(Mp > Mq) swap(Mp, Mq);
  272.         line<T> res(max(Lp, Mp), min(Lq, Mq));
  273.         if(res.d >= point<T>()) return static_cast<line<double>>(res);
  274.         return {};
  275.     }
  276.     auto rs = M.p - L.p ^ L.d;
  277.     if(s < 0) s = -s, ls = -ls, rs = -rs;
  278.     if(0 <= ls && ls <= s && 0 <= rs && rs <= s) return line<double>(static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d), point<double>());
  279.     else return {};
  280. }
  281. // Assumes nothing
  282. template<class T>
  283. optional<line<double>> intersect_open_segments(const line<T> &L, const line<T> &M){
  284.     auto s = L.d ^ M.d, ls = M.p - L.p ^ M.d;
  285.     if(!s){
  286.         if(ls) return {};
  287.         auto Lp = L.p, Lq = L.q(), Mp = M.p, Mq = M.q();
  288.         if(Lp > Lq) swap(Lp, Lq);
  289.         if(Mp > Mq) swap(Mp, Mq);
  290.         line<T> res(max(Lp, Mp), min(Lq, Mq));
  291.         if(res.d > point<T>()) return static_cast<line<double>>(res);
  292.         return {};
  293.     }
  294.     auto rs = (M.p - L.p) ^ L.d;
  295.     if(s < 0) s = -s, ls = -ls, rs = -rs;
  296.     if(0 < ls && ls < s && 0 < rs && rs < s) return line<double>(static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d), point<double>());
  297.     else return {};
  298. }
  299.  
  300. int main(){
  301.     cin.tie(0)->sync_with_stdio(0);
  302.     cin.exceptions(ios::badbit | ios::failbit);
  303.     cout << fixed << setprecision(15);
  304.     int n, m;
  305.     cin >> n >> m;
  306.     vector<pointll> large(n), small(m);
  307.     vector<long double> large_pref(n + 1);
  308.     for(auto i = 0; i < n; ++ i){
  309.         cin >> large[i];
  310.     }
  311.     auto next = [&](int i)->int{
  312.         ++ i;
  313.         if(i >= n){
  314.             i -= n;
  315.         }
  316.         return i;
  317.     };
  318.     for(auto i = 0; i < n; ++ i){
  319.         large_pref[i + 1] = large_pref[i] + distance(large[i], large[next(i)]);
  320.     }
  321.     for(auto i = 0; i < m; ++ i){
  322.         cin >> small[i];
  323.     }
  324.     long double res = 0;
  325.     for(auto i = 0, l = 0, r = 0; i < m; ++ i){
  326.         auto p = small[i], q = small[(i + 1) % m];
  327.         while(clockwise(p, q, large[l])){
  328.             l = next(l);
  329.         }
  330.         while(counterclockwise(p, q, large[next(l)])){
  331.             l = next(l);
  332.         }
  333.         while(counterclockwise(p, q, large[r])){
  334.             r = next(r);
  335.         }
  336.         while(clockwise(p, q, large[next(r)])){
  337.             r = next(r);
  338.         }
  339.         assert(l != r);
  340.         long double cur = l < r ? large_pref[r] - large_pref[l] : large_pref[n] - large_pref[l] + large_pref[r];
  341.         {
  342.             auto x = *intersect_no_parallel_overlap<0, 0, 0, 0>(lineld{p, q}, lineld{large[l], large[next(l)]});
  343.             cur -= distance<long double>(large[l], x);
  344.         }
  345.         {
  346.             auto x = *intersect_no_parallel_overlap<0, 0, 0, 0>(lineld{p, q}, lineld{large[r], large[next(r)]});
  347.             cur += distance<long double>(large[r], x);
  348.         }
  349.         res += distance(p, q) * cur;
  350.     }
  351.     cout << res / large_pref[n] << "\n";
  352.     return 0;
  353. }
  354.  
  355. /*
  356.  
  357. */
  358.  
  359. ////////////////////////////////////////////////////////////////////////////////////////
  360. //                                                                                    //
  361. //                                   Coded by Aeren                                   //
  362. //                                                                                    //
  363. ////////////////////////////////////////////////////////////////////////////////////////
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!