Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.39 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int K = 150000, N = 1000, MIN = -1, MAX = N * N + 1;
  7. const int lin[] = {-1, 0, 1,  0};
  8. const int col[] = { 0, 1, 0, -1};
  9.  
  10. struct nod
  11. {
  12.     int l, c;
  13. };
  14.  
  15. nod t, s1, s2, r1, r2;
  16. nod pas1, pas2;
  17. nod obs [K + 1];
  18. nod coada [N * N + 1];
  19. int n, k, lMaxZid, timpMin = MAX;
  20. int dR1 [N + 1][N + 1];
  21. int dR2 [N + 1][N + 1];
  22.  
  23. void citNod (nod &x)
  24. {
  25.     scanf ("%d %d", &x.l, &x.c);
  26. }
  27.  
  28. void bordare ()
  29. {
  30.     int i;
  31.  
  32.     for (i = 0; i < n + 2; i ++)
  33.         dR1[i][0] = dR1[i][n + 1] = dR1[0][i] = dR1[n + 1][i] = dR2[i][0] = dR2[i][n + 1] = dR2[0][i] = dR2[n + 1][i] = MIN;
  34. }
  35.  
  36. void marcObs ()
  37. {
  38.     int i;
  39.  
  40.     for (i = 1; i <= k; i ++)
  41.         dR1[obs[i].l][obs[i].c] = dR2[obs[i].l][obs[i].c] = MIN;
  42.  
  43.     dR1[t.l][t.c] = dR2[t.l][t.c] = MIN;
  44. }
  45.  
  46. void initMat ()
  47. {
  48.     bordare ();
  49.     marcObs ();
  50. }
  51.  
  52. nod getNod (int l, int c)
  53. {
  54.     nod x;
  55.  
  56.     x.l = l;
  57.     x.c = c;
  58.  
  59.     return x;
  60. }
  61.  
  62. void fillDR1 (nod x, int val)
  63. {
  64.     if (dR1[x.l][x.c] > val || dR1[x.l][x.c] == 0)
  65.     {
  66.         dR1[x.l][x.c] = val;
  67.  
  68.         int i;
  69.  
  70.         for (i = 0; i < 4; i ++)
  71.         {
  72.             nod no = getNod(x.l + lin[i], x.c + col[i]);
  73.             fillDR1(no, val + 1);
  74.         }
  75.     }
  76. }
  77.  
  78. void fillDR2 (nod x, int val)
  79. {
  80.     if (dR2[x.l][x.c] > val || dR2[x.l][x.c] == 0)
  81.     {
  82.         dR2[x.l][x.c] = val;
  83.  
  84.         int i;
  85.  
  86.         for (i = 0; i < 4; i ++)
  87.             fillDR2(getNod(x.l + lin[i], x.c + col[i]), val + 1);
  88.     }
  89. }
  90.  
  91. void setDr1 ()
  92. {
  93.     //fillDR1 (r1, 0);
  94.     int ic = 1, sf = 1, i;
  95.  
  96.     coada[1] = r1;
  97.  
  98.     while (ic <= sf)
  99.     {
  100.         for (i = 0; i < 4; i ++)
  101.             if (dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] != -1)
  102.                 if (dR1[coada[ic].l][coada[ic].c] + 1 < dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] || dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] == 0)
  103.                 {
  104.                     dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] = dR1[coada[ic].l][coada[ic].c] + 1;
  105.                     coada[++ sf] = getNod (coada[ic].l + lin[i], coada[ic].c + col [i]);
  106.                 }
  107.         ic ++;
  108.     }
  109. }
  110.  
  111. void setDr2 ()
  112. {
  113.     //fillDR2 (r2, 0);
  114.     int ic = 1, sf = 1, i;
  115.  
  116.     coada[1] = r2;
  117.  
  118.     while (ic <= sf)
  119.     {
  120.         for (i = 0; i < 4; i ++)
  121.             if (dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] != -1)
  122.                 if (dR2[coada[ic].l][coada[ic].c] + 1 < dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] || dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] == 0)
  123.                 {
  124.                     dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] = dR2[coada[ic].l][coada[ic].c] + 1;
  125.                     coada[++ sf] = getNod (coada[ic].l + lin[i], coada[ic].c + col [i]);
  126.                 }
  127.         ic ++;
  128.     }
  129. }
  130.  
  131. int cmmdc (int a, int b)
  132. {
  133.     int r;
  134.  
  135.     while (b != 0)
  136.     {
  137.         r = a % b;
  138.         a = b;
  139.         b = r;
  140.     }
  141.  
  142.     return a;
  143. }
  144.  
  145. int valpoz (int x)
  146. {
  147.     if (x > 0)
  148.         return x;
  149.     return - x;
  150. }
  151.  
  152. void calcPas1 ()
  153. {
  154.     int cd = cmmdc (s1.l - t.l, s1.c - t.c);
  155.  
  156.     pas1 = getNod ((s1.l - t.l) / cd, (s1.c - t.c) / cd);
  157.  
  158.     if (s1.l > t.l)
  159.         pas1.l = - valpoz (pas1.l);
  160.     else
  161.         pas1.l =  valpoz (pas1.l);
  162.  
  163.     if (s1.c > t.c)
  164.         pas1.c = - valpoz (pas1.c);
  165.     else
  166.         pas1.c =  valpoz (pas1.c);
  167. }
  168.  
  169. void calcPas2 ()
  170. {
  171.     int cd = cmmdc (s2.l - t.l, s2.c - t.c);
  172.  
  173.     pas2 = getNod ((s2.l - t.l) / cd, (s2.c - t.c) / cd);
  174.  
  175.     if (s2.l > t.l)
  176.         pas2.l = - valpoz (pas2.l);
  177.     else
  178.         pas2.l =  valpoz (pas2.l);
  179.  
  180.     if (s2.c > t.c)
  181.         pas2.c = - valpoz (pas2.c);
  182.     else
  183.         pas2.c =  valpoz (pas2.c);
  184. }
  185.  
  186. void init ()
  187. {
  188.     int i;
  189.  
  190.     freopen ("ai.in", "r", stdin);
  191.     freopen ("ai.out", "w", stdout);
  192.  
  193.     scanf ("%d", &n);
  194.     citNod (t);
  195.     citNod (s1);
  196.     citNod (s2);
  197.     citNod (r1);
  198.     citNod (r2);
  199.     scanf ("%d", &k);
  200.  
  201.     for (i = 1; i <= k; i ++)
  202.         citNod (obs[i]);
  203.  
  204.     initMat ();
  205.  
  206.     setDr1 ();
  207.     setDr2 ();
  208.  
  209.     calcPas1 ();
  210.     calcPas2 ();
  211. }
  212.  
  213. bool sortDupaL (const nod nod1, const nod nod2)
  214. {
  215.     if (nod1.l == nod2.l)
  216.         return nod1.c < nod2.c;
  217.     return nod1.l < nod2.l;
  218. }
  219.  
  220. bool sortDupaC (const nod nod1, const nod nod2)
  221. {
  222.     if (nod1.c == nod2.c)
  223.         return nod1.l < nod2.l;
  224.     return nod1.c < nod2.c;
  225. }
  226.  
  227. void sortL ()
  228. {
  229.     sort (obs + 1, obs + k + 1, sortDupaL);
  230. }
  231.  
  232. void sortC ()
  233. {
  234.     sort (obs + 1, obs + k + 1, sortDupaC);
  235. }
  236.  
  237. int getSecvMaxL ()
  238. {
  239.     int i, l = 1, lmax = 0;
  240.  
  241.     for (i = 1; i <= k; i ++)
  242.         if (obs[i].l == obs[i + 1].l && obs[i].c == obs[i + 1].c - 1)
  243.             l++;
  244.         else
  245.         {
  246.             if (l > lmax)
  247.                 lmax = l;
  248.             l = 1;
  249.         }
  250.     if (l > lmax)
  251.         lmax = l;
  252.  
  253.     return lmax;
  254. }
  255.  
  256. int getSecvMaxC ()
  257. {
  258.     int i, l = 1, lmax = 0;
  259.  
  260.     for (i = 1; i <= k; i ++)
  261.     {
  262.         if (obs [i].l == 37 && obs [i].c == 2)
  263.             obs [i].l = 37;
  264.  
  265.         if (obs[i].c == obs[i + 1].c && obs[i].l == obs[i + 1].l - 1)
  266.             l++;
  267.         else
  268.         {
  269.             if (l > lmax)
  270.                 lmax = l;
  271.             l = 1;
  272.         }
  273.     }
  274.     if (l > lmax)
  275.         lmax = l;
  276.  
  277.     return lmax;
  278. }
  279.  
  280. int getLMaxZid ()
  281. {
  282.     int aux1, aux2;
  283.     sortL ();
  284.     aux1 = getSecvMaxL ();
  285.  
  286.     sortC ();
  287.     aux2 = getSecvMaxC ();
  288.  
  289.     if (aux1 > aux2)
  290.         return aux1;
  291.     return aux2;
  292. }
  293.  
  294. int maxVal (int a, int b)
  295. {
  296.     if (a > b)
  297.         return a;
  298.     return b;
  299. }
  300.  
  301. int caz12 ()
  302. {
  303.     int l = s1.l, c = s1.c;
  304.     int min1 = MAX, min2 = MAX;
  305.  
  306.     //l += pas1.l;
  307.     //c += pas1.c;
  308.  
  309.     do
  310.     {
  311.         if (dR1[l][c] < min1 && dR1[l][c] > 0)
  312.             min1 = dR1[l][c];
  313.  
  314.         l += pas1.l;
  315.         c += pas1.c;
  316.     }
  317.     while (l != t.l || c != t.c);
  318.  
  319.     l = s2.l;
  320.     c = s2.c;
  321.  
  322.    // l += pas2.l;
  323.     //c += pas2.c;
  324.  
  325.     do
  326.     {
  327.         if (dR2[l][c] < min2 && dR1[l][c] > 0)
  328.             min2 = dR2[l][c];
  329.  
  330.         l += pas2.l;
  331.         c += pas2.c;
  332.     }
  333.     while (l != t.l || c != t.c);
  334.  
  335.     return maxVal(min1, min2);
  336. }
  337.  
  338. int caz21 ()
  339. {
  340.     int l = s1.l, c = s1.c;
  341.     int min1 = MAX, min2 = MAX;
  342.  
  343.    /* l += pas1.l;
  344.     c += pas1.c;*/
  345.  
  346.     do
  347.     {
  348.         if (dR2[l][c] < min1 && dR2[l][c] > 0)
  349.             min1 = dR2[l][c];
  350.  
  351.         l += pas1.l;
  352.         c += pas1.c;
  353.     }
  354.     while (l != t.l || c != t.c);
  355.  
  356.     l = s2.l;
  357.     c = s2.c;
  358.  
  359.    /* l += pas2.l;
  360.     c += pas2.c;*/
  361.  
  362.     do
  363.     {
  364.         if (dR1[l][c] < min2 && dR1 [l][c] > 0)
  365.             min2 = dR1[l][c];
  366.  
  367.         l += pas2.l;
  368.         c += pas2.c;
  369.     }
  370.     while (l != t.l || c != t.c);
  371.  
  372.     return maxVal(min1, min2);
  373. }
  374.  
  375. nod mij (nod n1, nod n2, nod n3)
  376. {
  377.     if (n2.l <= n1.l && n1.l <= n3.l || n2.l >= n1.l && n1.l >= n3.l)
  378.         return n1;
  379.  
  380.     if (n1.l <= n2.l && n2.l <= n3.l || n1.l >= n2.l && n2.l >= n3.l)
  381.         return n2;
  382.  
  383.     if (n1.l <= n3.l && n3.l <= n2.l || n1.l >= n3.l && n3.l >= n2.l)
  384.         return n3;
  385. }
  386.  
  387. bool mijB (nod n1, nod n2, nod n3)
  388. {
  389.     nod no = mij (n1, n2, n3);
  390.     if (no.l == n1.l && no.c == n1.c)
  391.         return true;
  392.     return false;
  393. }
  394.  
  395. bool coliniare (nod n1, nod n2, nod n3)
  396. {
  397.     nod no = mij (n1, n2, n3);
  398.     if ((n2.l - n1.l) * (n3.c - n2.c) == (n3.l - n2.l) * (n2.c - n1.c))
  399.         if (n3.l != no.l || n3.c != no.c)
  400.             return true;
  401.     return false;
  402. }
  403.  
  404. int caz1 ()
  405. {
  406.     nod s, pas;
  407.     int min1 = MAX;
  408.     int l, c;
  409.  
  410.     if (coliniare (s1, s2, t))
  411.     {
  412.         if(mijB (s1, s2, t))
  413.         {
  414.             pas = pas1;
  415.             s = s1;
  416.         }
  417.         else
  418.         {
  419.             pas = pas2;
  420.             s = s2;
  421.         }
  422.  
  423.         l = s.l;
  424.         c = s.c;
  425.  
  426.         /*l += pas.l;
  427.         c += pas.c;*/
  428.  
  429.         do
  430.         {
  431.             if (dR1[l][c] < min1 && dR1[l][c] > 0)
  432.                 min1 = dR1[l][c];
  433.  
  434.             l += pas.l;
  435.             c += pas.c;
  436.         }
  437.         while (l != t.l || c != t.c);
  438.  
  439.         return min1;
  440.     }
  441.  
  442.     return MAX;
  443. }
  444.  
  445. int caz2 ()
  446. {
  447.     nod s, pas;
  448.     int min1 = MAX;
  449.     int l, c;
  450.  
  451.     if (coliniare (s1, s2, t))
  452.     {
  453.         if(mijB (s1, s2, t))
  454.         {
  455.             pas = pas1;
  456.             s = s1;
  457.         }
  458.         else
  459.         {
  460.             pas = pas2;
  461.             s = s2;
  462.         }
  463.  
  464.         l = s.l;
  465.         c = s.c;
  466.  
  467.         /*l += pas.l;
  468.         c += pas.c;*/
  469.  
  470.         do
  471.         {
  472.             if (dR2[l][c] < min1 && dR2[l][c] > 0)
  473.                 min1 = dR2[l][c];
  474.  
  475.             l += pas.l;
  476.             c += pas.c;
  477.         }
  478.         while (l != t.l || c != t.c);
  479.  
  480.         return min1;
  481.     }
  482.  
  483.     return MAX;
  484. }
  485.  
  486. int min4 (int a, int b, int c, int d)
  487. {
  488.     int min1 = a;
  489.     if (b < min1)
  490.         min1 = b;
  491.     if (c < min1)
  492.         min1 = c;
  493.     if (d < min1)
  494.         min1 = d;
  495.     return min1;
  496. }
  497.  
  498. int getTimpMin ()
  499. {
  500.     int aux1 = caz12 ();
  501.     int aux2 = caz21 ();
  502.     int aux3 = caz1 ();
  503.     int aux4 = caz2 ();
  504.  
  505.     return min4 (aux1, aux2, aux3, aux4);
  506. }
  507.  
  508. void solve ()
  509. {
  510.     lMaxZid = getLMaxZid ();
  511.     timpMin = getTimpMin ();
  512. }
  513.  
  514. void afis ()
  515. {
  516.     printf ("%d\n", lMaxZid);
  517.     printf ("%d", timpMin);
  518. }
  519.  
  520. int main ()
  521. {
  522.     init ();
  523.     solve ();
  524.     afis ();
  525.  
  526.     return 0;
  527. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement