G2A Many GEOs
SHARE
TWEET

Untitled

a guest Mar 29th, 2020 82 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.     if(duration.count() > 2500) cerr << duration.count() << endl;
  169.     return duration.count() > 2500;
  170. }
  171.  
  172. long long solveIt(int st, int en){
  173.     if(dp[st][en] != -1) return dp[st][en];
  174.     if(en-st <= 2) return dp[st][en] = 0;
  175.     dp[st][en] = INF/5;
  176.     for(int m = st+1; m <= en-1; m++)
  177.         if(allowed[st][m] && allowed[m][en])
  178.             dp[st][en] = min(dp[st][en], solveIt(st, m)+solveIt(m, en)+costs[st][m]+costs[m][en]);
  179.     return dp[st][en];
  180. }
  181.  
  182. int main(){
  183.     //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  184.     ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  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.         for(int j = 0; j < N; j++) dp[i][j] = -1;
  192.     }
  193.     startTime = chrono::high_resolution_clock::now();
  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] = allowed[v][u] = true;
  198.                 costs[u][v] = costs[v][u] = 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.             // Check if the segment overlaps with or intersects any side of the polygon
  203.             seg ourseg = seg(point(points[u].f, points[u].s), point(points[v].f, points[v].s));
  204.             bool ok = true;
  205.             for(int j = 0; j < polygon.size(); j++){
  206.                 point p; seg temp;
  207.                 if(overlap(ourseg, polygon[j], temp) && temp.l.d != zero){
  208.                     ok = false;
  209.                     break;
  210.                 }
  211.                 if(intersect(ourseg, polygon[j], p) && p != ourseg.l.p && p != ourseg.l.p+ourseg.l.d){
  212.                     ok = false;
  213.                     break;
  214.                 }
  215.             }
  216.             // Check if some point on the segment is within bounds of the polygon
  217.             point m = ourseg.l.p+ourseg.l.d/2;
  218.             point oof; oof.x = m.x+100000; oof.y = m.y+99999;
  219.             seg dummy(m, oof);
  220.             int numInter = 0;
  221.             point p;
  222.             for(seg s : polygon) numInter += intersect(s, dummy, p);
  223.             ok &= numInter&1;
  224.             // Final verdict
  225.             allowed[u][v] = allowed[v][u] = ok;
  226.             //cout << points[u].f << ' ' << points[u].s << ' ' << points[v].f << ' ' << points[v].s << " | " << allowed[u][v] << endl;
  227.         }
  228.     //if(tooLate()) assert(false);
  229.     ret = solveIt(0, N-1);
  230.     if(ret == INF/5) cout << "impossible\n";
  231.     else cout << ret << '\n';
  232.     return 0;
  233. }
  234.  
  235. /******************************
  236. Kateba ii dake no hanashi darou
  237. Success is only a victory away
  238. - No Game No Life Opening
  239. ******************************/
RAW Paste Data
Ledger Nano X - The secure hardware wallet
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