Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 29th, 2020 87 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. struct rat {
  31.     ll n, d;
  32.     rat() : n(0), d(1) {}
  33.     rat(ll x) : n(x), d(1) {}
  34.     rat(ll _n, ll _d) : n(_n), d(_d) {
  35.         if (n == 0) d = 1;
  36.         else {
  37.             ll g = __gcd(abs(n), abs(d));
  38.             n /= g, d /= g;
  39.             if (d<0) n*=-1, d*=-1;
  40.         }
  41.     }
  42.     rat(const rat& r) : n(r.n), d(r.d) {}
  43.     rat operator -() const { return rat(-n, d); }
  44.     operator ld() const { return double(n) / d; }
  45.     template<typename T> rat operator +(T o) const {
  46.         rat r(o); return rat(n*r.d+r.n*d,d*r.d); }
  47.     template<typename T> rat operator -(T o) const {
  48.         return (*this)+(-o); }
  49.     template<typename T> rat operator *(T o) const {
  50.         rat r(o); return rat(n*r.n, d*r.d); }
  51.     template<typename T> rat operator /(T o) const {
  52.         rat r(o); return rat(n*r.d, d*r.n); }
  53.     template<typename T> bool operator ==(T o) const {
  54.         rat r(o); return n == r.n && d == r.d; }
  55.     template<typename T> bool operator !=(T o) const {
  56.         return !((*this) == o); }
  57.     template<typename T> bool operator <(T o) const {
  58.         rat r(o); return n*r.d < r.n*d; }
  59.     template<typename T> bool operator >(T o) const {
  60.         return !(*this == o) && !(*this < o); }
  61.     template<typename T> bool operator <=(T o) const {
  62.         return *this < o || *this == o; }
  63.     template<typename T> bool operator >=(T o) const {
  64.         return *this > o || *this == o; }
  65. };
  66. istream& operator >>(istream& is, rat& r) { ll a; is >> a; r = rat(a); return is; }
  67. /* HPEND */
  68.  
  69. /* HPSTART {"title": "Point", "section": "Geometry", "snippet": "point"} */
  70. typedef rat cord;
  71. typedef pair<cord, cord> point;
  72.  
  73. cord dot(point a, point b) {
  74.     return a.x*b.x + a.y*b.y; }
  75. cord cross(point a, point b) {
  76.     return a.x*b.y - a.y*b.x; }
  77. cord norm(point p) { return dot(p, p); }
  78. ld abs(point p) { return sqrt(norm(p)); }
  79. point conj(point p) { return point(p.x,-p.y); }
  80. point operator +(const point& a, const point& b) {
  81.     return point(a.x+b.x, a.y+b.y); }
  82. point operator -(const point& a, const point& b) {
  83.     return point(a.x-b.x, a.y-b.y); }
  84. point operator *(const cord& l, const point& r) {
  85.     return point(l*r.x, l*r.y); }
  86. point operator *(const point& l, const cord& r) {
  87.     return r*l; }
  88. point operator /(const point& p, const cord& s) {
  89.     return point(p.x/s, p.y/s); }
  90. /* HPEND */
  91.  
  92. /* HPSTART {"title": "Lines and Segments", "section": "Geometry", "snippet": "lines"} */
  93. struct line {
  94.     point p, d;
  95.     line() {}
  96.     line(point a, point b) : p(a), d(b-a) {}
  97.     point eval(cord t) { return p + t*d; }
  98.     operator bool() { return d != point(); }
  99. };
  100.  
  101. struct seg {
  102.     line l;
  103.     seg() {}
  104.     seg(point a, point b) : l(a, b) {}
  105. };
  106.  
  107. // be careful with precision here
  108. bool on_line(line l, point p, cord& t) {
  109.     if (!l) {
  110.         t = 0; return p == l.p;
  111.     }
  112.     if (cross(p - l.p, l.d) != 0) return false;
  113.     t = dot(p - l.p, l.d) / norm(l.d);
  114.     return true;
  115. }
  116.  
  117. bool on_segment(seg s, point p) {
  118.     if (!s.l) return p == s.l.p;
  119.     cord t;
  120.     // if (!on_line(s.l, p, t)) return false;
  121.     point a = s.l.p, b = s.l.p+s.l.d;
  122.     return p.x >= min(a.x,b.x) && p.x <= max(a.x,b.x) &&
  123.         p.y >= min(a.y,b.y) && p.y <= max(a.y,b.y);
  124. }
  125.  
  126. bool intersect(line l1, line l2, point& p) {
  127.     if (!l2) swap(l1, l2);
  128.     if (!l1) {
  129.         p = l1.p; cord t;
  130.         return on_line(l2, l1.p, t);
  131.     }
  132.     if (cross(l1.d, l2.d) == 0) return false;
  133.     cord i = cross(l2.p-l1.p, l2.d) / cross(l1.d, l2.d);
  134.     p = l1.p + i*l1.d;
  135.     return true;
  136. }
  137.  
  138. bool intersect(seg s1, seg s2, point& p) {
  139.     if (!intersect(s1.l, s2.l, p)) return false;
  140.     return on_segment(s1, p) && on_segment(s2, p);
  141. }
  142.  
  143. bool overlap(seg s1, seg s2, seg& r) {
  144.     if (cross(s1.l.d, s2.l.d) != 0) return false;
  145.     cord t0, t1;
  146.     if (!on_line(s1.l, s2.l.p, t0)) return false;
  147.     on_line(s1.l, s2.l.p+s2.l.d, t1);
  148.     if (t0>t1) swap(t0,t1);
  149.     cord a = max(cord(0), t0), b = min(cord(1), t1);
  150.     if (a <= b) {
  151.         r = seg(s1.l.eval(a), s1.l.eval(b));
  152.         return true;
  153.     }
  154.     return false;
  155. }
  156.  
  157. int N;
  158. pair<long long, long long> points [210];
  159. vector<seg> polygon;
  160. bool allowed [210][210];
  161. long long costs [210][210], dp [210][210], ret = INF/5;
  162. point zero(0, 0);
  163. chrono::time_point<chrono::high_resolution_clock> startTime;
  164.  
  165. bool tooLate(){
  166.     auto endTime = chrono::high_resolution_clock::now();
  167.     auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
  168.     return duration.count() > 2500;
  169. }
  170.  
  171. long long solveIt(int st, int en){
  172.     if(dp[st][en] != -1) return dp[st][en];
  173.     if(en-st <= 2) return dp[st][en] = 0;
  174.     dp[st][en] = INF/5;
  175.     for(int m = st+1; m <= en-1; m++)
  176.         if(allowed[st][m] && allowed[m][en])
  177.             dp[st][en] = min(dp[st][en], solveIt(st, m)+solveIt(m, en)+costs[st][m]+costs[m][en]);
  178.     return dp[st][en];
  179. }
  180.  
  181. int main(){
  182.     //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  183.     ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  184.     startTime = chrono::high_resolution_clock::now();
  185.     cin >> N; for(int i = 0; i < N; i++) cin >> points[i].f >> points[i].s;
  186.     for(int i = 0; i < N; i++){
  187.         point a, b;
  188.         a.x = points[i].f, a.y = points[i].s;
  189.         b.x = points[(i+1)%N].f, b.y = points[(i+1)%N].s;
  190.         polygon.pb(seg(a, b));
  191.         allowed[i][i] = true; allowed[i][(i+1)%N] = true;
  192.         for(int j = 0; j < N; j++) dp[i][j] = -1;
  193.     }
  194.     for(int u = 0; u < N; u++)
  195.         for(int v = 0; v <= u; v++){
  196.             if(u == v || u == (v+1)%N || v == (u+1)%N){
  197.                 allowed[u][v] = true;
  198.                 costs[u][v] = 0;
  199.                 continue;
  200.             }
  201.             costs[u][v] = costs[v][u] = pow(points[u].f-points[v].f, 2)+pow(points[u].s-points[v].s, 2);
  202.             vector<seg> segments;
  203.             segments.pb(seg(point(points[u].f, points[u].s), point(points[v].f, points[v].s)));
  204.             assert((int)segments.size() == 1);
  205.             bool ok = true;
  206.             for(int i = 0; i < (int)segments.size(); i++)
  207.                 for(int j = 0; j < polygon.size(); j++){
  208.                     assert(i == 0);
  209.                     //if(tooLate()) assert(false);
  210.                     point p; seg temp;
  211.                     if(overlap(segments[i], polygon[j], temp) && temp.l.d != zero){
  212.                         ok = false;
  213.                         break;
  214.                     }
  215.                     if(intersect(segments[i], polygon[j], p) && p != segments[i].l.p && p != segments[i].l.p+segments[i].l.d){
  216.                         ok = false;
  217.                         break;
  218.                     }
  219.                 }
  220.             for(int i = 0; i < (int)segments.size(); i++){
  221.                 for(int iter = 1; iter < 2; iter++){
  222.                     assert(i == 0);
  223.                     //if(tooLate()) assert(false);
  224.                     point m = segments[i].l.p+(segments[i].l.d*iter)/2;
  225.                     point oof; oof.x = m.x+100000; oof.y = m.y+99999;
  226.                     seg dummy(m, oof);
  227.                     int numInter = 0;
  228.                     point p;
  229.                     for(seg s : polygon) numInter += intersect(s, dummy, p);
  230.                     ok &= numInter&1;
  231.                 }
  232.             }
  233.             allowed[u][v] = allowed[v][u] = ok;
  234.             //cout << points[u].f << ' ' << points[u].s << ' ' << points[v].f << ' ' << points[v].s << " | " << allowed[u][v] << endl;
  235.         }
  236.     ret = solveIt(0, N-1);
  237.     if(ret == INF/5) cout << "impossible\n";
  238.     else cout << ret << '\n';
  239.     return 0;
  240. }
  241.  
  242. /******************************
  243. Kateba ii dake no hanashi darou
  244. Success is only a victory away
  245. - No Game No Life Opening
  246. ******************************/
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