Advertisement
ec1117

Untitled

Oct 7th, 2020
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef double db;
  7. typedef string str;
  8.  
  9. typedef pair<int,int> pi;
  10. typedef pair<pi, int> pii;
  11. typedef pair<ll,ll> pl;
  12. typedef pair<db,db> pd;
  13.  
  14. typedef vector<int> vi;
  15. typedef vector<bool> vb;
  16. typedef vector<ll> vl;
  17. typedef vector<db> vd;
  18. typedef vector<str> vs;
  19. typedef vector<pi> vpi;
  20. typedef vector<pl> vpl;
  21. typedef vector<pd> vpd;
  22. template<class T> using V = vector<T>;
  23. template<class T, size_t SZ> using AR = array<T,SZ>;
  24.  
  25. #define mp make_pair
  26. #define f first
  27. #define s second
  28. #define sz(x) (int)(x).size()
  29. #define all(x) begin(x), end(x)
  30. #define rall(x) (x).rbegin(), (x).rend()
  31. #define sor(x) sort(all(x))
  32. #define rsz resize
  33. #define ins insert
  34. #define ft front()
  35. #define bk back()
  36. #define pf push_front
  37. #define pb push_back
  38. #define eb emplace_back
  39. #define lb lower_bound
  40. #define ub upper_bound
  41.  
  42. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  43. #define F0R(i,a) FOR(i,0,a)
  44. #define For(i,a) FOR(i,0,a)
  45. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  46. #define R0F(i,a) ROF(i,0,a)
  47. #define Rof(i,a) ROF(i,0,a)
  48. #define trav(a,x) for (auto& a: x)
  49.  
  50. template<class T> bool ckmin(T& a, const T& b) {
  51.         return b < a ? a = b, 1 : 0; }
  52. template<class T> bool ckmax(T& a, const T& b) {
  53.         return a < b ? a = b, 1 : 0; }
  54. constexpr int pct(int x) { return __builtin_popcount(x); }
  55. constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
  56. ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
  57. ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
  58. ll half(ll x) { return fdiv(x,2); }
  59.  
  60. template<class T, class U> T fstTrue(T lo, T hi, U f) {
  61. // note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
  62.         hi ++; assert(lo <= hi); // assuming f is increasing
  63.         while (lo < hi) { // find first index such that f is true
  64.                 T mid = half(lo+hi);
  65.                 f(mid) ? hi = mid : lo = mid+1;
  66.         }
  67.         return lo;
  68. }
  69. template<class T, class U> T lstTrue(T lo, T hi, U f) {
  70.         lo --; assert(lo <= hi); // assuming f is decreasing
  71.         while (lo < hi) { // find first index such that f is true
  72.                 T mid = half(lo+hi+1);
  73.                 f(mid) ? lo = mid : hi = mid-1;
  74.         }
  75.         return lo;
  76. }
  77. template<class T> void remDup(vector<T>& v) {
  78.         sort(all(v)); v.erase(unique(all(v)),end(v)); }
  79.  
  80. // INPUT
  81. template<class A> void re(complex<A>& c);
  82. template<class A, class B> void re(pair<A,B>& p);
  83. template<class A> void re(vector<A>& v);
  84. template<class A, size_t SZ> void re(array<A,SZ>& a);
  85.  
  86. template<class T> void re(T& x) { cin >> x; }
  87. void re(db& d) { str t; re(t); d = stod(t); }
  88. void re(ld& d) { str t; re(t); d = stold(t); }
  89. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  90.  
  91. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  92. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  93. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  94. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  95.  
  96. // TO_STRING
  97. #define ts to_string
  98. str ts(char c) { return str(1,c); }
  99. str ts(const char* s) { return (str)s; }
  100. str ts(str s) { return s; }
  101. str ts(bool b) {
  102. #ifdef LOCAL
  103.         return b ? "true" : "false";
  104. #else
  105.         return ts((int)b);
  106. #endif
  107. }
  108. template<class A> str ts(complex<A> c) {
  109.         stringstream ss; ss << c; return ss.str(); }
  110. str ts(vector<bool> v) {
  111.         str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  112.         res += "}"; return res; }
  113. template<size_t SZ> str ts(bitset<SZ> b) {
  114.         str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  115.         return res; }
  116. template<class A, class B> str ts(pair<A,B> p);
  117. template<class T> str ts(T v) { // containers with begin(), end()
  118. #ifdef LOCAL
  119.         bool fst = 1; str res = "{";
  120.         for (const auto& x: v) {
  121.                 if (!fst) res += ", ";
  122.                 fst = 0; res += ts(x);
  123.         }
  124.         res += "}"; return res;
  125. #else
  126.         bool fst = 1; str res = "";
  127.         for (const auto& x: v) {
  128.             if (!fst) res += " ";
  129.             fst = 0; res += ts(x);
  130.         }
  131.         return res;
  132.  
  133. #endif
  134. }
  135. template<class A, class B> str ts(pair<A,B> p) {
  136. #ifdef LOCAL
  137.         return "("+ts(p.f)+", "+ts(p.s)+")";
  138. #else
  139.         return ts(p.f)+" "+ts(p.s);
  140. #endif
  141. }
  142.  
  143. // OUTPUT
  144. template<class A> void pr(A x) { cout << ts(x); }
  145. template<class H, class... T> void pr(const H& h, const T&... t) {
  146.         pr(h); pr(t...); }
  147. void ps() { pr("\n"); } // print w/ spaces
  148. template<class H, class... T> void ps(const H& h, const T&... t) {
  149.         pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  150.  
  151. // DEBUG
  152. void DBG() { cerr << "]" << endl; }
  153. template<class H, class... T> void DBG(H h, T... t) {
  154.         cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  155.         DBG(t...); }
  156. #ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
  157. #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  158. #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
  159.          << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
  160. #else
  161. #define dbg(...) 0
  162.     #define chk(...) 0
  163. #endif
  164.  
  165. int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}
  166. int max(int a,int b, int c){return max(a,max(b,c));}
  167. int min(int a,int b, int c){return min(a,min(b,c));}
  168.  
  169. // FILE I/O
  170. void setIn(str s) { freopen(s.c_str(),"r",stdin); }
  171. void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  172. void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
  173. void setIO(str s = "") {
  174.         unsyncIO();
  175. // cin.exceptions(cin.failbit);
  176. // throws exception when do smth illegal
  177. // ex. try to read letter into int
  178.         if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  179. }
  180.  
  181. const int MOD = 1e9+7; // 998244353;
  182. const int MX = 2e5+5;
  183. const ll INF = 1e18;
  184. const ld PI = acos((ld)-1);
  185. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
  186. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  187.  
  188. vpi adj[MX];
  189. int main() {
  190.         setIO();
  191.         int n,m;re(n,m);
  192.         int A,B,C,D;re(A,B,C,D);
  193.         pi xp[m],yp[m];
  194.         int X[m],Y[m];
  195.         For(i,m){
  196.                 re(X[i],Y[i]);
  197.                 xp[i]=mp(X[i],i);
  198.                 yp[i]=mp(Y[i],i);
  199.         }
  200.         sort(xp,xp+m);
  201.         sort(yp,yp+m);
  202.         For(i,m-1){
  203.                 adj[xp[i].s].pb(mp(xp[i+1].s, abs(xp[i+1].f-xp[i].f)));
  204.                 adj[xp[i+1].s].pb(mp(xp[i].s, abs(xp[i+1].f-xp[i].f)));
  205.         }
  206.         For(i,m-1){
  207.                 adj[yp[i].s].pb(mp(yp[i+1].s, abs(yp[i+1].f-yp[i].f)));
  208.                 adj[yp[i+1].s].pb(mp(yp[i].s, abs(yp[i+1].f-yp[i].f)));
  209.         }
  210.  
  211.         priority_queue<pl, vpl, greater<pl> > pq;
  212.         int dist[MX];memset(dist,MOD,sizeof dist);
  213.         For(i,m){
  214.                 pq.push(mp(min(abs(X[i]-A),abs(Y[i]-B)),i));
  215.         }
  216.         while(!pq.empty()){
  217.                 pi tmp=pq.top();pq.pop();
  218.                 if(tmp.f>dist[tmp.s])continue;
  219.                 dist[tmp.s]=tmp.f;
  220.                 trav(x,adj[tmp.s]){
  221.                         if(tmp.f+x.s<dist[x.f]){
  222.                                 dist[x.f]=tmp.f+x.s;
  223.                                 pq.push(mp(dist[x.f],x.f));
  224.                         }
  225.                 }
  226.         }
  227.         int ret=abs(C-A)+abs(D-B);
  228.         For(i,m){
  229.                 ckmin(ret,dist[i]+abs(C-X[i])+abs(D-Y[i]));
  230.         }
  231.         ps(ret);
  232. // you should actually read the stuff at the bottom
  233. }
  234.  
  235. /* stuff you should look for
  236.     * int overflow, array bounds
  237.     * special cases (n=1?)
  238.     * do smth instead of nothing and stay organized
  239.     * WRITE STUFF DOWN
  240.     * DON'T GET STUCK ON ONE APPROACH
  241. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement