Advertisement
welleyth

Day6. A

Jul 5th, 2022
835
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.88 KB | None
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. //#define int long long
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. //#pragma GCC optimize("Ofast")
  12. //#pragma GCC optimize("unroll-loops")
  13. //#pragma GCC target("avx2")
  14.  
  15. constexpr long long INF = (long long)2e9;
  16. constexpr int N = (int)1e6 + 111;
  17. constexpr int md = (int)1e9 + 7;
  18. constexpr int mdPower = (int)1e9+7 - 1;
  19. constexpr int P = (int)998244343;
  20. constexpr double PI = acos(-1);
  21.  
  22. //typedef __int128 _uint;
  23. typedef long long ll;
  24.  
  25. mt19937_64 rnd(time(nullptr));
  26.  
  27. void add(int& a,int b){
  28.     a += b; if(a >= md) a -= md;
  29. }
  30. void sub(int& a,int b){
  31.     a -= b; while(a < 0) a += md;
  32. }
  33.  
  34. int bpow(int a,int b){
  35.     if(b == 0)
  36.         return 1;
  37.     if(b % 2 == 0){
  38.         int t = bpow(a,b>>1);
  39.         return 1ll*t*t%md;
  40.     }
  41.     return 1ll * a*bpow(a,b-1) % md;
  42. }
  43.  
  44. int inv(int a){
  45.     return bpow(a,md-2);
  46. }
  47.  
  48. //int fac[N],invfac[N];
  49. //
  50. //void init(){
  51. //    fac[0] = 1;
  52. //    for(int i = 1; i < N; i++){
  53. //        fac[i] = (fac[i-1] * i) % md;
  54. //    }
  55. //    invfac[N-1] = inv(fac[N-1]);
  56. //    for(int i = N-2; i >= 0; i--){
  57. //        invfac[i] = (invfac[i+1] * (i+1))%md;
  58. //    }
  59. //    return;
  60. //}
  61. //
  62. //int C(int n,int k){
  63. //    if(k > n)
  64. //        return 0;
  65. //    return fac[n] * invfac[k] % md * invfac[n-k] % md;
  66. //}
  67. //
  68. //int A(int n,int k){
  69. //    if(k > n)
  70. //        return 0;
  71. //    return fac[n] * invfac[n-k] % md;
  72. //}
  73.  
  74. struct pt{
  75.     int x,y;
  76.     pt(){}
  77.     pt(int x,int y):x(x),y(y){}
  78. };
  79.  
  80. int sg(int x){
  81.     if(x == 0)
  82.         return 0;
  83.     if(x < 0)
  84.         return -1;
  85.     if(x > 0)
  86.         return 1;
  87.     return 0;
  88. }
  89.  
  90. int src(pt a,pt b,pt c){
  91.     pt v1 = pt(b.x-a.x,b.y-a.y);
  92.     pt v2 = pt(c.x-a.x,c.y-a.y);
  93.     return sg(v1.x * v2.y - v1.y  * v2.x);
  94. }
  95.  
  96. bool intersect1(int a,int b,int c,int d){
  97.     if(a > b) swap(a,b);
  98.     if(c > d) swap(c,d);
  99.     return max(a,c) <= min(b,d);
  100. }
  101.  
  102. bool intersect(pt a1,pt a2,pt b1,pt b2){
  103.     return intersect1(a1.x,a2.x,b1.x,b2.x)
  104.         && intersect1(a1.y,a2.y,b1.y,b2.y)
  105.         && sg(src(a1,a2,b1) * src(a1,a2,b2)) == -1
  106.         && sg(src(b1,b2,a1) * src(b1,b2,a2)) == -1;
  107. }
  108.  
  109. long double dist(pt a,pt b){
  110.     int d1 = a.x - b.x;
  111.     int d2 = a.y - b.y;
  112.     return sqrt(d1 * d1 + d2 * d2);
  113. }
  114.  
  115. constexpr int K = 12 * 12;
  116.  
  117. pt InnerPolygon[2*K];
  118. pt OuterPolygon[2*K];
  119.  
  120. pt Polygon[2][2*K];
  121.  
  122. long double dp[2][2*K];
  123. int n,m;
  124.  
  125. bool LiesInInnerPolygon(pt a){
  126.     set<int> st;
  127.     for(int i = 0; i < n; i++){
  128.         st.insert(src(Polygon[0][i],Polygon[0][i+1],a));
  129.     }
  130.     st.erase(0);
  131.     return st.size() == 1;
  132. }
  133.  
  134. void solve(){
  135.     cin >> n;
  136.  
  137.     for(int i = 0; i < n; i++){
  138.         cin >> Polygon[0][i].x >> Polygon[0][i].y;
  139.     }
  140.     cin >> m;
  141.     for(int i = 0; i < m; i++){
  142.         cin >> Polygon[1][i].x >> Polygon[1][i].y;
  143.     }
  144.     for(int i = n; i < 2*K; i++){
  145.         Polygon[0][i] = Polygon[0][i-n];
  146.     }
  147.     for(int i = m; i < 2*K; i++){
  148.         Polygon[1][i] = Polygon[1][i-m];
  149.     }
  150.  
  151.     vector<pair<pt,pt>> Segments;
  152.     for(int i = 0; i < n; i++){
  153.         Segments.pb(mp(Polygon[0][i],Polygon[0][i+1]));
  154.     }
  155.     for(int i = 0; i < m; i++){
  156.         Segments.pb(mp(Polygon[1][i],Polygon[1][i+1]));
  157.     }
  158.  
  159.     int sz[2] = {n,m};
  160.     long double ans = INF;
  161.  
  162.     for(int l = 0; l < 2; l++){
  163.         for(int i = 0; i < sz[l]; i++){
  164.             for(int j = 0; j < 2*K; j++){
  165.                 dp[0][j] = dp[1][j] = INF;
  166.             }
  167.             dp[l][i] = 0;
  168.             for(int j = i; j < i + K; j++){
  169.                 for(int t1 = 0; t1 < 2; t1++){
  170.                     if(dp[t1][j] == INF)
  171.                         continue;
  172.                     pt p1 = Polygon[t1][j];
  173.                     cerr << "curPt = " << p1.x << " " << p1.y << "\n";
  174.                     for(int k = j; k < i+K; k++){
  175.                         for(int t2 = 0; t2 < 2; t2++){
  176.                             if(t1 == t2 && (k >= j + 3 || k >= i + sz[t1] - 1))
  177.                                 break;
  178.                             if(t1 == t2 && k%sz[t1] == j%sz[t1])
  179.                                 continue;
  180.                             pt p2 = Polygon[t2][k];
  181.                             bool ok = true;
  182.                             for(auto&[s1,s2] : Segments){
  183.                                 if(intersect(p1,p2,s1,s2)){
  184.                                     ok = false;
  185. //                                    cerr << p1.x << " " << p1.y << " " << p2.x << " " << p2.y;
  186. //                                    cerr << " intersects with ";
  187. //                                    cerr << s1.x << " " << s1.y << " " << s2.x << " " << s2.y;
  188. //                                    cerr << "\n";
  189.                                     break;
  190.                                 }
  191.                             }
  192.                             if(ok){
  193.                                 cerr << Polygon[t1][j].x << " " << Polygon[t1][j].y << " -> ";
  194.                                 cerr << Polygon[t2][k].x << " " << Polygon[t2][k].y << "\n\n";
  195.                                 dp[t2][k] = min(dp[t2][k],dp[t1][j]+dist(p1,p2));
  196.                             }
  197.                         }
  198.                     }
  199.                 }
  200.             }
  201.             cerr << "!!!!!!!!!!!!!!!!!" << l << " " << i << "\n";
  202.             for(int j = i+sz[l]; j < 2*K; j += sz[l]){
  203.                 ans = min(ans,dp[l][j]);
  204.             }
  205.             cerr << "ans = " << ans << "\n";
  206.         }
  207.     }
  208.  
  209.     cout << fixed << setprecision(15) << ans << "\n";
  210.  
  211.     return;
  212. }
  213.  
  214. signed main(){
  215.     ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  216.     int tests = 1;
  217. //    cin >> tests;
  218.     for(int test = 1; test <= tests; test++){
  219. //        cerr << "test = " << test << "\n";
  220.         solve();
  221.     }
  222.     return 0;
  223. }
  224. /**
  225. 6 8
  226. 1 2
  227. 2 4
  228. 4 5
  229. 5 6
  230. 6 4
  231. 4 2
  232. 2 3
  233. 3 1
  234. ))((()
  235.  
  236. **/
  237.  
Advertisement
RAW Paste Data Copied
Advertisement