Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- const int K = 150000, N = 1000, MIN = -1, MAX = N * N + 1;
- const int lin[] = {-1, 0, 1, 0};
- const int col[] = { 0, 1, 0, -1};
- struct nod
- {
- int l, c;
- };
- nod t, s1, s2, r1, r2;
- nod pas1, pas2;
- nod obs [K + 1];
- nod coada [N * N + 1];
- int n, k, lMaxZid, timpMin = MAX;
- int dR1 [N + 1][N + 1];
- int dR2 [N + 1][N + 1];
- void citNod (nod &x)
- {
- scanf ("%d %d", &x.l, &x.c);
- }
- void bordare ()
- {
- int i;
- for (i = 0; i < n + 2; i ++)
- 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;
- }
- void marcObs ()
- {
- int i;
- for (i = 1; i <= k; i ++)
- dR1[obs[i].l][obs[i].c] = dR2[obs[i].l][obs[i].c] = MIN;
- dR1[t.l][t.c] = dR2[t.l][t.c] = MIN;
- }
- void initMat ()
- {
- bordare ();
- marcObs ();
- }
- nod getNod (int l, int c)
- {
- nod x;
- x.l = l;
- x.c = c;
- return x;
- }
- void fillDR1 (nod x, int val)
- {
- if (dR1[x.l][x.c] > val || dR1[x.l][x.c] == 0)
- {
- dR1[x.l][x.c] = val;
- int i;
- for (i = 0; i < 4; i ++)
- {
- nod no = getNod(x.l + lin[i], x.c + col[i]);
- fillDR1(no, val + 1);
- }
- }
- }
- void fillDR2 (nod x, int val)
- {
- if (dR2[x.l][x.c] > val || dR2[x.l][x.c] == 0)
- {
- dR2[x.l][x.c] = val;
- int i;
- for (i = 0; i < 4; i ++)
- fillDR2(getNod(x.l + lin[i], x.c + col[i]), val + 1);
- }
- }
- void setDr1 ()
- {
- //fillDR1 (r1, 0);
- int ic = 1, sf = 1, i;
- coada[1] = r1;
- while (ic <= sf)
- {
- for (i = 0; i < 4; i ++)
- if (dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] != -1)
- 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)
- {
- dR1[coada[ic].l + lin[i]][coada[ic].c + col[i]] = dR1[coada[ic].l][coada[ic].c] + 1;
- coada[++ sf] = getNod (coada[ic].l + lin[i], coada[ic].c + col [i]);
- }
- ic ++;
- }
- }
- void setDr2 ()
- {
- //fillDR2 (r2, 0);
- int ic = 1, sf = 1, i;
- coada[1] = r2;
- while (ic <= sf)
- {
- for (i = 0; i < 4; i ++)
- if (dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] != -1)
- 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)
- {
- dR2[coada[ic].l + lin[i]][coada[ic].c + col[i]] = dR2[coada[ic].l][coada[ic].c] + 1;
- coada[++ sf] = getNod (coada[ic].l + lin[i], coada[ic].c + col [i]);
- }
- ic ++;
- }
- }
- int cmmdc (int a, int b)
- {
- int r;
- while (b != 0)
- {
- r = a % b;
- a = b;
- b = r;
- }
- return a;
- }
- int valpoz (int x)
- {
- if (x > 0)
- return x;
- return - x;
- }
- void calcPas1 ()
- {
- int cd = cmmdc (s1.l - t.l, s1.c - t.c);
- pas1 = getNod ((s1.l - t.l) / cd, (s1.c - t.c) / cd);
- if (s1.l > t.l)
- pas1.l = - valpoz (pas1.l);
- else
- pas1.l = valpoz (pas1.l);
- if (s1.c > t.c)
- pas1.c = - valpoz (pas1.c);
- else
- pas1.c = valpoz (pas1.c);
- }
- void calcPas2 ()
- {
- int cd = cmmdc (s2.l - t.l, s2.c - t.c);
- pas2 = getNod ((s2.l - t.l) / cd, (s2.c - t.c) / cd);
- if (s2.l > t.l)
- pas2.l = - valpoz (pas2.l);
- else
- pas2.l = valpoz (pas2.l);
- if (s2.c > t.c)
- pas2.c = - valpoz (pas2.c);
- else
- pas2.c = valpoz (pas2.c);
- }
- void init ()
- {
- int i;
- freopen ("ai.in", "r", stdin);
- freopen ("ai.out", "w", stdout);
- scanf ("%d", &n);
- citNod (t);
- citNod (s1);
- citNod (s2);
- citNod (r1);
- citNod (r2);
- scanf ("%d", &k);
- for (i = 1; i <= k; i ++)
- citNod (obs[i]);
- initMat ();
- setDr1 ();
- setDr2 ();
- calcPas1 ();
- calcPas2 ();
- }
- bool sortDupaL (const nod nod1, const nod nod2)
- {
- if (nod1.l == nod2.l)
- return nod1.c < nod2.c;
- return nod1.l < nod2.l;
- }
- bool sortDupaC (const nod nod1, const nod nod2)
- {
- if (nod1.c == nod2.c)
- return nod1.l < nod2.l;
- return nod1.c < nod2.c;
- }
- void sortL ()
- {
- sort (obs + 1, obs + k + 1, sortDupaL);
- }
- void sortC ()
- {
- sort (obs + 1, obs + k + 1, sortDupaC);
- }
- int getSecvMaxL ()
- {
- int i, l = 1, lmax = 0;
- for (i = 1; i <= k; i ++)
- if (obs[i].l == obs[i + 1].l && obs[i].c == obs[i + 1].c - 1)
- l++;
- else
- {
- if (l > lmax)
- lmax = l;
- l = 1;
- }
- if (l > lmax)
- lmax = l;
- return lmax;
- }
- int getSecvMaxC ()
- {
- int i, l = 1, lmax = 0;
- for (i = 1; i <= k; i ++)
- {
- if (obs [i].l == 37 && obs [i].c == 2)
- obs [i].l = 37;
- if (obs[i].c == obs[i + 1].c && obs[i].l == obs[i + 1].l - 1)
- l++;
- else
- {
- if (l > lmax)
- lmax = l;
- l = 1;
- }
- }
- if (l > lmax)
- lmax = l;
- return lmax;
- }
- int getLMaxZid ()
- {
- int aux1, aux2;
- sortL ();
- aux1 = getSecvMaxL ();
- sortC ();
- aux2 = getSecvMaxC ();
- if (aux1 > aux2)
- return aux1;
- return aux2;
- }
- int maxVal (int a, int b)
- {
- if (a > b)
- return a;
- return b;
- }
- int caz12 ()
- {
- int l = s1.l, c = s1.c;
- int min1 = MAX, min2 = MAX;
- //l += pas1.l;
- //c += pas1.c;
- do
- {
- if (dR1[l][c] < min1 && dR1[l][c] > 0)
- min1 = dR1[l][c];
- l += pas1.l;
- c += pas1.c;
- }
- while (l != t.l || c != t.c);
- l = s2.l;
- c = s2.c;
- // l += pas2.l;
- //c += pas2.c;
- do
- {
- if (dR2[l][c] < min2 && dR1[l][c] > 0)
- min2 = dR2[l][c];
- l += pas2.l;
- c += pas2.c;
- }
- while (l != t.l || c != t.c);
- return maxVal(min1, min2);
- }
- int caz21 ()
- {
- int l = s1.l, c = s1.c;
- int min1 = MAX, min2 = MAX;
- /* l += pas1.l;
- c += pas1.c;*/
- do
- {
- if (dR2[l][c] < min1 && dR2[l][c] > 0)
- min1 = dR2[l][c];
- l += pas1.l;
- c += pas1.c;
- }
- while (l != t.l || c != t.c);
- l = s2.l;
- c = s2.c;
- /* l += pas2.l;
- c += pas2.c;*/
- do
- {
- if (dR1[l][c] < min2 && dR1 [l][c] > 0)
- min2 = dR1[l][c];
- l += pas2.l;
- c += pas2.c;
- }
- while (l != t.l || c != t.c);
- return maxVal(min1, min2);
- }
- nod mij (nod n1, nod n2, nod n3)
- {
- if (n2.l <= n1.l && n1.l <= n3.l || n2.l >= n1.l && n1.l >= n3.l)
- return n1;
- if (n1.l <= n2.l && n2.l <= n3.l || n1.l >= n2.l && n2.l >= n3.l)
- return n2;
- if (n1.l <= n3.l && n3.l <= n2.l || n1.l >= n3.l && n3.l >= n2.l)
- return n3;
- }
- bool mijB (nod n1, nod n2, nod n3)
- {
- nod no = mij (n1, n2, n3);
- if (no.l == n1.l && no.c == n1.c)
- return true;
- return false;
- }
- bool coliniare (nod n1, nod n2, nod n3)
- {
- nod no = mij (n1, n2, n3);
- if ((n2.l - n1.l) * (n3.c - n2.c) == (n3.l - n2.l) * (n2.c - n1.c))
- if (n3.l != no.l || n3.c != no.c)
- return true;
- return false;
- }
- int caz1 ()
- {
- nod s, pas;
- int min1 = MAX;
- int l, c;
- if (coliniare (s1, s2, t))
- {
- if(mijB (s1, s2, t))
- {
- pas = pas1;
- s = s1;
- }
- else
- {
- pas = pas2;
- s = s2;
- }
- l = s.l;
- c = s.c;
- /*l += pas.l;
- c += pas.c;*/
- do
- {
- if (dR1[l][c] < min1 && dR1[l][c] > 0)
- min1 = dR1[l][c];
- l += pas.l;
- c += pas.c;
- }
- while (l != t.l || c != t.c);
- return min1;
- }
- return MAX;
- }
- int caz2 ()
- {
- nod s, pas;
- int min1 = MAX;
- int l, c;
- if (coliniare (s1, s2, t))
- {
- if(mijB (s1, s2, t))
- {
- pas = pas1;
- s = s1;
- }
- else
- {
- pas = pas2;
- s = s2;
- }
- l = s.l;
- c = s.c;
- /*l += pas.l;
- c += pas.c;*/
- do
- {
- if (dR2[l][c] < min1 && dR2[l][c] > 0)
- min1 = dR2[l][c];
- l += pas.l;
- c += pas.c;
- }
- while (l != t.l || c != t.c);
- return min1;
- }
- return MAX;
- }
- int min4 (int a, int b, int c, int d)
- {
- int min1 = a;
- if (b < min1)
- min1 = b;
- if (c < min1)
- min1 = c;
- if (d < min1)
- min1 = d;
- return min1;
- }
- int getTimpMin ()
- {
- int aux1 = caz12 ();
- int aux2 = caz21 ();
- int aux3 = caz1 ();
- int aux4 = caz2 ();
- return min4 (aux1, aux2, aux3, aux4);
- }
- void solve ()
- {
- lMaxZid = getLMaxZid ();
- timpMin = getTimpMin ();
- }
- void afis ()
- {
- printf ("%d\n", lMaxZid);
- printf ("%d", timpMin);
- }
- int main ()
- {
- init ();
- solve ();
- afis ();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement