Advertisement
Guest User

Untitled

a guest
Dec 13th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cctype>
  8. #include <cstring>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <algorithm>
  17. #include <iterator>
  18. #include <bitset>
  19. #include <ctime>
  20. using namespace std;
  21.  
  22. #define F(i, n) for(int i = 0; i < n; ++i)
  23. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  24. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  25. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  26. #define FILL(a,value) memset(a, value, sizeof(a))
  27.  
  28. #define SZ(a) (int)a.size()
  29. #define ALL(a) a.begin(), a.end()
  30. #define PB push_back
  31. #define MP make_pair
  32.  
  33. typedef long long LL;
  34. typedef vector<int> VI;
  35. typedef pair<int, int> PII;
  36.  
  37. const double PI = acos(-1.0);
  38. const int INF = 1000 * 1000 * 1000 + 7;
  39. const LL LINF = INF * (LL) INF;
  40.  
  41. const int MAX = 3*5555;
  42.  
  43.  
  44. struct point
  45. {
  46.     int x, y;
  47.     point(int x = 0, int y = 0) : x(x), y(y) {}
  48.     point operator-(const point& p)const
  49.     {
  50.         return point(x-p.x, y-p.y);
  51.     }
  52.     int operator*(const point& p)const
  53.     {
  54.         return x * p.y - y * p.x;
  55.     }
  56.     int dot(const point& p)const
  57.     {
  58.         return x * p.x + y * p.x;
  59.     }
  60.     point operator-()const
  61.     {
  62.         return point()-*this;
  63.     }
  64. };
  65.  
  66. bool par(const point& A, const point &B)
  67. {
  68.     return (A * B) == 0 && A.dot(B) >= 0;
  69. }
  70.  
  71. bool in_range(const point& A, const point & B, bool a, bool b, const point& X)
  72. {
  73.     if (par(A, X))return a;
  74.     if (par(X, B))return b;
  75.     if ((A * B) < 0)
  76.         return (A * X) > 0 || (X * B) > 0;
  77.     return (A * X) > 0 && (X * B) > 0;
  78. }
  79.  
  80. point P[22];
  81. int main()
  82. {
  83.     //freopen("in.txt", "r", stdin);
  84.     FOR(i, 0, 4)
  85.         FOR(j, 0, 4)
  86.     {
  87.         int x;
  88.         cin >> x;
  89.         --x;
  90.         P[x] = point(j, i);
  91.     }
  92.     point L, R;
  93.     L = R = P[1] - P[0];
  94.     bool l = 1, r = 1;
  95.     int ans = 1;
  96.     FOR(i, 1, 15)
  97.     {
  98.         if (in_range(L, R, l, r, P[i+1] - P[i]))
  99.         {
  100.             L = R = P[i+1] - P[i];
  101.             l = r = 1;
  102.         }
  103.         else
  104.         {
  105.             ans++;
  106.             point NL = -L;
  107.             point NR = -R;
  108.             l = r = 0;
  109.             if (!in_range(NL, NR, 0, 0, P[i+1] - P[i]))
  110.             {
  111.                 if (in_range(R, NL, 1, 1, P[i+1] - P[i]))
  112.                 {
  113.                     NL = P[i+1] - P[i];
  114.                     l = 1;
  115.                 }
  116.                 else
  117.                 {
  118.                     NR = P[i+1] - P[i];
  119.                     r = 1;
  120.                 }
  121.             }
  122.             L = NL;
  123.             R = NR;
  124.         }
  125.     }
  126.     cout << ans << endl;
  127.    
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement