Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.91 KB | None | 0 0
  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. ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement