Advertisement
Guest User

Untitled

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