Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 30th, 2020 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. template <class T>
  10. using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  11. template <class T>
  12. using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  13.  
  14. #define PI atan2(0, -1)
  15. #define epsilon 1e-9
  16. #define INF 5e18
  17. #define MOD 1000000007
  18.  
  19. #define mp make_pair
  20. #define pb push_back
  21. #define f first
  22. #define s second
  23. #define lb lower_bound
  24. #define ub upper_bound
  25.  
  26. #define ll long long
  27. #define ld long double
  28. #define x first
  29. #define y second
  30.  
  31. struct rat {
  32.     ll n, d;
  33.     rat() : n(0), d(1) {}
  34.     rat(ll x) : n(x), d(1) {}
  35.     rat(ll _n, ll _d) : n(_n), d(_d) {
  36.         if (n == 0) d = 1;
  37.         else {
  38.             ll g = __gcd(abs(n), abs(d));
  39.             n /= g, d /= g;
  40.             if (d<0) n*=-1, d*=-1;
  41.         }
  42.     }
  43.     rat(const rat& r) : n(r.n), d(r.d) {}
  44.     rat operator -() const { return rat(-n, d); }
  45.     operator ld() const { return double(n) / d; }
  46.     template<typename T> rat operator +(T o) const {
  47.         rat r(o); return rat(n*r.d+r.n*d,d*r.d); }
  48.     template<typename T> rat operator -(T o) const {
  49.         return (*this)+(-o); }
  50.     template<typename T> rat operator *(T o) const {
  51.         rat r(o); return rat(n*r.n, d*r.d); }
  52.     template<typename T> rat operator /(T o) const {
  53.         rat r(o); return rat(n*r.d, d*r.n); }
  54.     template<typename T> bool operator ==(T o) const {
  55.         rat r(o); return n == r.n && d == r.d; }
  56.     template<typename T> bool operator !=(T o) const {
  57.         return !((*this) == o); }
  58.     template<typename T> bool operator <(T o) const {
  59.         rat r(o); return n*r.d < r.n*d; }
  60.     template<typename T> bool operator >(T o) const {
  61.         return !(*this == o) && !(*this < o); }
  62.     template<typename T> bool operator <=(T o) const {
  63.         return *this < o || *this == o; }
  64.     template<typename T> bool operator >=(T o) const {
  65.         return *this > o || *this == o; }
  66. };
  67. istream& operator >>(istream& is, rat& r) { ll a; is >> a; r = rat(a); return is; }
  68.  
  69. typedef rat cord;
  70. typedef pair<cord, cord> point;
  71.  
  72. cord dot(point a, point b) {
  73.     return a.x*b.x + a.y*b.y; }
  74. cord cross(point a, point b) {
  75.     return a.x*b.y - a.y*b.x; }
  76. cord norm(point p) { return dot(p, p); }
  77. ld abs(point p) { return sqrt(norm(p)); }
  78. point conj(point p) { return point(p.x,-p.y); }
  79. point operator +(const point& a, const point& b) {
  80.     return point(a.x+b.x, a.y+b.y); }
  81. point operator -(const point& a, const point& b) {
  82.     return point(a.x-b.x, a.y-b.y); }
  83. point operator *(const cord& l, const point& r) {
  84.     return point(l*r.x, l*r.y); }
  85. point operator *(const point& l, const cord& r) {
  86.     return r*l; }
  87. point operator /(const point& p, const cord& s) {
  88.     return point(p.x/s, p.y/s); }
  89.  
  90. struct line {
  91.     point p, d;
  92.     line() {}
  93.     line(point a, point b) : p(a), d(b-a) {}
  94.     point eval(cord t) { return p + t*d; }
  95.     operator bool() { return d != point(); }
  96. };
  97.  
  98. struct seg {
  99.     line l;
  100.     seg() {}
  101.     seg(point a, point b) : l(a, b) {}
  102. };
  103.  
  104. // be careful with precision here
  105. bool on_line(line l, point p, cord& t) {
  106.     if (!l) {
  107.         t = 0; return p == l.p;
  108.     }
  109.     if (cross(p - l.p, l.d) != 0) return false;
  110.     t = dot(p - l.p, l.d) / norm(l.d);
  111.     return true;
  112. }
  113.  
  114. bool on_segment(seg s, point p) {
  115.     if (!s.l) return p == s.l.p;
  116.     cord t;
  117.     // if (!on_line(s.l, p, t)) return false;
  118.     point a = s.l.p, b = s.l.p+s.l.d;
  119.     return p.x >= min(a.x,b.x) && p.x <= max(a.x,b.x) &&
  120.         p.y >= min(a.y,b.y) && p.y <= max(a.y,b.y);
  121. }
  122.  
  123. bool intersect(line l1, line l2, point& p) {
  124.     if (!l2) swap(l1, l2);
  125.     if (!l1) {
  126.         p = l1.p; cord t;
  127.         return on_line(l2, l1.p, t);
  128.     }
  129.     if (cross(l1.d, l2.d) == 0) return false;
  130.     cord i = cross(l2.p-l1.p, l2.d) / cross(l1.d, l2.d);
  131.     p = l1.p + i*l1.d;
  132.     return true;
  133. }
  134.  
  135. bool intersect(seg s1, seg s2, point& p) {
  136.     if (!intersect(s1.l, s2.l, p)) return false;
  137.     return on_segment(s1, p) && on_segment(s2, p);
  138. }
  139.  
  140. bool overlap(seg s1, seg s2, seg& r) {
  141.     if (cross(s1.l.d, s2.l.d) != 0) return false;
  142.     cord t0, t1;
  143.     if (!on_line(s1.l, s2.l.p, t0)) return false;
  144.     on_line(s1.l, s2.l.p+s2.l.d, t1);
  145.     if (t0>t1) swap(t0,t1);
  146.     cord a = max(cord(0), t0), b = min(cord(1), t1);
  147.     if (a <= b) {
  148.         r = seg(s1.l.eval(a), s1.l.eval(b));
  149.         return true;
  150.     }
  151.     return false;
  152. }
  153.  
  154. int N;
  155. point points [210];
  156. vector<seg> polygon;
  157. bool allowed [210][210];
  158. long long costs [210][210], dp [210][210], ret = INF/5;
  159. point zero(0, 0);
  160. chrono::time_point<chrono::high_resolution_clock> startTime;
  161.  
  162. bool tooLate(){
  163.     auto endTime = chrono::high_resolution_clock::now();
  164.     auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
  165.     if(duration.count() > 2500) cerr << duration.count() << endl;
  166.     return duration.count() > 2500;
  167. }
  168.  
  169. long long solveIt(int st, int en){
  170.     if(dp[st][en] != -1) return dp[st][en];
  171.     if(en-st <= 2) return dp[st][en] = 0;
  172.     dp[st][en] = INF/5;
  173.     for(int m = st+1; m <= en-1; m++)
  174.         if(allowed[st][m] && allowed[m][en])
  175.             dp[st][en] = min(dp[st][en], solveIt(st, m)+solveIt(m, en)+costs[st][m]+costs[m][en]);
  176.     return dp[st][en];
  177. }
  178.  
  179. int main(){
  180.     //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  181.     ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  182.     cin >> N; for(int i = 0; i < N; i++) cin >> points[i].x >> points[i].y;
  183.     for(int i = 0; i < N; i++){
  184.         polygon.pb(seg(points[i], points[(i+1)%N]));
  185.         for(int j = 0; j < N; j++) dp[i][j] = -1;
  186.     }
  187.     startTime = chrono::high_resolution_clock::now();
  188.     for(int u = 0; u < N; u++)
  189.         for(int v = 0; v <= u; v++){
  190.             if(u == v || u == (v+1)%N || v == (u+1)%N){
  191.                 allowed[u][v] = allowed[v][u] = true;
  192.                 costs[u][v] = costs[v][u] = 0;
  193.                 continue;
  194.             }
  195.             costs[u][v] = costs[v][u] = pow(points[u].f-points[v].f, 2)+pow(points[u].s-points[v].s, 2);
  196.             // Check if the segment overlaps with or intersects any side of the polygon
  197.             seg ourseg = seg(point(points[u].f, points[u].s), point(points[v].f, points[v].s));
  198.             bool ok = true;
  199.             for(int j = 0; j < (int)polygon.size(); j++){
  200.                 point p; seg temp;
  201.                 if(overlap(ourseg, polygon[j], temp) && temp.l.d != zero){
  202.                     ok = false;
  203.                     break;
  204.                 }
  205.                 if(intersect(ourseg, polygon[j], p) && p != ourseg.l.p && p != ourseg.l.p+ourseg.l.d){
  206.                     ok = false;
  207.                     break;
  208.                 }
  209.             }
  210.             // Check if some point on the segment is within bounds of the polygon
  211.             point m = ourseg.l.p+ourseg.l.d/2;
  212.             rat ta(100000), tb(99999);
  213.             point oof; oof.x = m.x+ta; oof.y = m.y+tb;
  214.             seg dummy(m, oof);
  215.             int numInter = 0;
  216.             point p;
  217.             for(int j = 0; j < (int)polygon.size(); j++) numInter += intersect(polygon[j], dummy, p);
  218.             ok &= numInter&1;
  219.             // Final verdict
  220.             allowed[u][v] = allowed[v][u] = ok;
  221.             //cout << points[u].f << ' ' << points[u].s << ' ' << points[v].f << ' ' << points[v].s << " | " << allowed[u][v] << endl;
  222.         }
  223.     //if(tooLate()) assert(false);
  224.     ret = solveIt(0, N-1);
  225.     if(ret == INF/5) cout << "impossible\n";
  226.     else cout << ret << '\n';
  227.     return 0;
  228. }
  229.  
  230. /******************************
  231. Kateba ii dake no hanashi darou
  232. Success is only a victory away
  233. - No Game No Life Opening
  234. ******************************/
RAW Paste Data
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
Top