Advertisement
Guest User

ГЕОМА-ГОВНО

a guest
Dec 3rd, 2016
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <ctime>
  6. #include <vector>
  7. #include <queue>
  8. #include <bitset>
  9. #include <cmath>
  10. #include <time.h>
  11. #include <set>
  12. #include <map>
  13. #include <unordered_set>
  14. #include <unordered_map>
  15. #include <stdlib.h>
  16. #include <deque>
  17. #include <iomanip>
  18. #include <complex>
  19. #include <cassert>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef long double ld;
  25. #define _GLIBCXX_DEBUG
  26. #define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
  27. #define all(v) v.begin(), v.end()
  28. #define randInt ((rand() << 15) | rand())
  29. #define For(i, n) for (int i = 0; i < n; i++)
  30. #define whatIs(x) cout << #x << " is " << x << endl
  31. #define in(s) freopen(s, "r", stdin)
  32. #define out(s) freopen(s, "w", stdout)
  33. #define mp(x, y) make_pair(x, y)
  34. #define fi first
  35. #define se second
  36.  
  37. int nod(int a, int b)
  38. {
  39.     return a ? nod(b % a, a) : b;
  40. }
  41.  
  42. int nok(int a, int b)
  43. {
  44.     return a / nod(a, b) * b;
  45. }
  46.  
  47. string intToStr(ll n)
  48. {
  49.     return n ? intToStr(n / 10) + (char)('0' + n % 10) : "";
  50. }
  51.  
  52. long long sum(vector<int> v)
  53. {
  54.     int ans = 0;
  55.     For(i, v.size())
  56.         ans += v[i];
  57.     return ans;
  58. }
  59.  
  60. bool prime(int n)
  61. {
  62.     if (n == 1)
  63.         return false;
  64.     for (int i = 2; i <= sqrt(n); i++)
  65.         if (n % i == 0)
  66.             return false;
  67.     return true;
  68. }
  69.  
  70. bool letter(char c)
  71. {
  72.     return 'a' <= c && c <= 'z';
  73. }
  74.  
  75. bool LETTER(char c)
  76. {
  77.     return 'A' <= c && c <= 'Z';
  78. }
  79.  
  80. bool digit(char c)
  81. {
  82.     return ('0' <= c && c <= '9');
  83. }
  84.  
  85. ll stringToInt(string s)
  86. {
  87.     ll ans = 0;
  88.     for (int i = 0; i < s.size(); i++)
  89.         ans = 10 * ans + digit(s[i]);
  90.     return ans;
  91. }
  92.  
  93. const ld pi = 3.141592653589793238462643383279;
  94. const ld eps = 1e-8;
  95. const ld zero = 0;
  96. const ll null = 0;
  97. const ll INF = 1e18;
  98. //const int INF = 1e9;
  99. const ll MOD = 1000000007;
  100. const int BIG = 1e9;
  101. const int alf = 26;
  102. const int MAXN = 200001;
  103. const int MAXM = 1001;
  104. const int dx[4] = {-1, 0, 1, 0};
  105. const int dy[4] = {0, 1, 0, -1};
  106. const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  107. const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  108. const string alphabet = "abcdefghijklmnopqrstuvwxyz";
  109. const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  110.  
  111. struct point
  112. {
  113.     ld x;
  114.     ld y;
  115. };
  116.  
  117. struct line
  118. {
  119.     ld a, b, c;
  120. };
  121.  
  122. ld dist(point a, point b)
  123. {
  124.     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  125. }
  126.  
  127. point makePoint(ld x, ld y)
  128. {
  129.     point p;
  130.     p.x = x;
  131.     p.y = y;
  132.     return p;
  133. }
  134.  
  135. line makeLine(ld a, ld b, ld c)
  136. {
  137.     line ans;
  138.     ans.a = a;
  139.     ans.b = b;
  140.     ans.c = c;
  141.     return ans;
  142. }
  143.  
  144. line makeLine(point A, point B)
  145. {
  146.     line l;
  147.     l.a = A.y - B.y;
  148.     l.b = B.x - A.x;
  149.     l.c = -l.a * A.x - l.b * A.y;
  150.     return l;
  151. }
  152.  
  153. bool linesParallel(line l1, line l2)
  154. {
  155.     return l1.a * l2.b == l2.a * l1.b;
  156. }
  157.  
  158. point linesCross(line l1, line l2)
  159. {
  160.     point p;
  161.     p.y = (l1.a * l2.c - l2.a * l1.c) / (l2.a * l1.b - l1.a * l2.b);
  162.     if (l1.a != 0)
  163.         p.x = (-l1.b * p.y - l1.c) / l1.a;
  164.     else
  165.         p.x = (-l2.b * p.y - l2.c) / l2.a;
  166.     return p;
  167. }
  168.  
  169. ld f(vector<point> a)
  170. {
  171.     if (a.size() < 3)
  172.         return (ld)(0);
  173.     ld ans = 0;
  174.     for (int i = 0; i < a.size(); i++)
  175.         ans += (a[(i + 1) % (int)(a.size())].x - a[i].x) * (a[(i + 1) % (int)(a.size())].y + a[i].y) / 2;
  176.     return abs(ans);
  177. }
  178.  
  179. vector< pair<int, int> > a, b;
  180. vector< pair< int, pair<int, int> > > v;
  181.  
  182. vector<int> ans, ans2;
  183.  
  184. vector<point> c;
  185.  
  186. ld epsilon = 1e-10;
  187.  
  188. int main()
  189. {
  190.     fastRead;
  191.     int n, m;
  192.     cin >> n >> m;
  193.     a.resize(n);
  194.     b.resize(m);
  195.     for (int i = 0; i < n; i++)
  196.         cin >> a[i].fi >> a[i].se;
  197.     for (int i = 0; i < m; i++)
  198.         cin >> b[i].fi >> b[i].se;
  199.     ld dy = 1e9;
  200.     for (int i = 0; i < n; i++)
  201.     {
  202.         int l = 0, r = m - 1;
  203.         while(r - l > 1)
  204.         {
  205.             int med = (r + l) / 2;
  206.             if (b[med].fi >= a[i].fi)
  207.                 r = med;
  208.             else
  209.                 l = med;
  210.         }
  211.         line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
  212.         ld y = (-l1.a * (ld)(a[i].fi) - l1.c) / l1.b;
  213.         if (abs(abs((ld)(a[i].se) - y) - dy) < epsilon)
  214.             ans.push_back(i);
  215.         else if (abs((ld)(a[i].se) - y) < dy)
  216.         {
  217.             ans.clear();
  218.             ans.push_back(i);
  219.             dy = abs((ld)(a[i].se) - y);
  220.         }
  221.     }
  222.     int answ = 0;
  223.     if (ans.size() > 0 && ans[0] != 0)
  224.         answ++;
  225.     if (ans.size() > 0 && ans[ans.size() - 1] != n - 1)
  226.         answ++;
  227.     for (int i = 0; i < (int)(ans.size()) - 1; i++)
  228.         if (ans[i] != ans[i + 1] - 1)
  229.             answ++;
  230.         else
  231.         {
  232.             int l = 0, r = m - 1;
  233.             while(r - l > 1)
  234.             {
  235.                 int med = (r + l) / 2;
  236.                 if (b[med].fi >= a[ans[i]].fi)
  237.                     r = med;
  238.                 else
  239.                     l = med;
  240.             }
  241.             line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
  242.             ld x1 = a[ans[i]].fi;
  243.             int t1 = l;
  244.             ld y1 = (-l1.a * (ld)(a[ans[i]].fi) - l1.c) / l1.b;
  245.             l = 0;
  246.             r = m - 1;
  247.             while(r - l > 1)
  248.             {
  249.                 int med = (r + l) / 2;
  250.                 if (b[med].fi >= a[ans[i + 1]].fi)
  251.                     r = med;
  252.                 else
  253.                     l = med;
  254.             }
  255.             l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
  256.             ld x2 = a[ans[i + 1]].fi;
  257.             int t2 = l;
  258.             ld y2 = (-l1.a * (ld)(a[ans[i + 1]].fi) - l1.c) / l1.b;
  259.             c.clear();
  260.             c.push_back(makePoint(x1, y1));
  261.             for (int j = t1 + 1; j <= t2; j++)
  262.                 c.push_back(makePoint(b[j].fi, b[j].se));
  263.             c.push_back(makePoint(x2, y2));
  264.             if (f(c) > eps)
  265.                 answ++;
  266.         }
  267.     int best = answ;
  268.     ans2 = ans;
  269.     ans.clear();
  270.     bool ok = false;
  271.     for (int i = 0; i < m; i++)
  272.     {
  273.         int l = 0, r = n - 1;
  274.         while(r - l > 1)
  275.         {
  276.             int med = (r + l) / 2;
  277.             if (a[med].fi >= b[i].fi)
  278.                 r = med;
  279.             else
  280.                 l = med;
  281.         }
  282.         line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
  283.         ld y = (-l1.a * (ld)(b[i].fi) - l1.c) / l1.b;
  284.         if (abs(abs((ld)(b[i].se) - y) - dy) < epsilon)
  285.             ans.push_back(i);
  286.         else if (abs((ld)(b[i].se) - y) < dy)
  287.         {
  288.             ok = true;
  289.             ans.clear();
  290.             ans.push_back(i);
  291.             dy = abs((ld)(b[i].se) - y);
  292.         }
  293.     }
  294.     answ = 0;
  295.     if (ans.size() > 0 && ans[0] != 0)
  296.         answ++;
  297.     if (ans.size() > 0 && ans[ans.size() - 1] != m - 1)
  298.         answ++;
  299.     for (int i = 0; i < (int)(ans.size()) - 1; i++)
  300.         if (ans[i] != ans[i + 1] - 1)
  301.             answ++;
  302.         else
  303.         {
  304.             int l = 0, r = n - 1;
  305.             while(r - l > 1)
  306.             {
  307.                 int med = (r + l) / 2;
  308.                 if (a[med].fi >= b[ans[i]].fi)
  309.                     r = med;
  310.                 else
  311.                     l = med;
  312.             }
  313.             line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
  314.             ld x1 = b[ans[i]].fi;
  315.             int t1 = l;
  316.             ld y1 = (-l1.a * (ld)(b[ans[i]].fi) - l1.c) / l1.b;
  317.             l = 0;
  318.             r = n - 1;
  319.             while(r - l > 1)
  320.             {
  321.                 int med = (r + l) / 2;
  322.                 if (b[med].fi >= b[ans[i + 1]].fi)
  323.                     r = med;
  324.                 else
  325.                     l = med;
  326.             }
  327.             l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
  328.             ld x2 = b[ans[i + 1]].fi;
  329.             int t2 = l;
  330.             ld y2 = (-l1.a * (ld)(b[ans[i + 1]].fi) - l1.c) / l1.b;
  331.             c.clear();
  332.             c.push_back(makePoint(x1, y1));
  333.             for (int j = t1 + 1; j <= t2; j++)
  334.                 c.push_back(makePoint(a[j].fi, a[j].se));
  335.             c.push_back(makePoint(x2, y2));
  336.             if (f(c) > eps)
  337.                 answ++;
  338.         }
  339.     if (ok)
  340.         best = answ;
  341.     else if (ans.size() > 0)
  342.     {
  343.         for (int i = 0; i < ans2.size(); i++)
  344.             v.push_back({a[ans2[i]].fi, {ans2[i], 1}});
  345.         for (int i = 0; i < ans.size(); i++)
  346.             v.push_back({b[ans[i]].fi, {ans[i], 2}});
  347.         sort(v.begin(), v.end());
  348.         answ = 0;
  349.         if (v.size() > 0 && v[0].se.fi != 0)
  350.             answ++;
  351.         if (v.size() > 0 && (v[v.size() - 1].se.fi != n - 1 || v[v.size() - 1].se.se != 1) && (v[v.size() - 1].se.fi != m - 1 || v[v.size() - 1].se.se != 2))
  352.             answ++;
  353.         for (int i = 0; i < (int)(v.size()) - 1; i++)
  354.         {
  355.             ld x1, y1, x2, y2;
  356.             int t1a, t1b, t2a, t2b;
  357.             if (v[i].se.se == 1)
  358.             {
  359.                 int l = 0, r = m - 1;
  360.                 while(r - l > 1)
  361.                 {
  362.                     int med = (r + l) / 2;
  363.                     if (b[med].fi >= a[v[i].se.fi].fi)
  364.                         r = med;
  365.                     else
  366.                         l = med;
  367.                 }
  368.                 line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
  369.                 x1 = a[v[i].se.fi].fi;
  370.                 t1b = l + 1;
  371.                 t1a = v[i].se.fi;
  372.                 y1 = (-l1.a * (ld)(a[v[i].se.fi].fi) - l1.c) / l1.b + dy;
  373.             }
  374.             else
  375.             {
  376.                 int l = 0, r = n - 1;
  377.                 while(r - l > 1)
  378.                 {
  379.                     int med = (r + l) / 2;
  380.                     if (a[med].fi >= b[v[i].se.fi].fi)
  381.                         r = med;
  382.                     else
  383.                         l = med;
  384.                 }
  385.                 line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
  386.                 x1 = b[v[i].se.fi].fi;
  387.                 t1a = l + 1;
  388.                 t1b = v[i].se.fi;
  389.                 y1 = (-l1.a * (ld)(b[v[i].se.fi].fi) - l1.c) / l1.b;
  390.             }
  391.             i++;
  392.             if (v[i].se.se == 1)
  393.             {
  394.                 int l = 0, r = m - 1;
  395.                 while(r - l > 1)
  396.                 {
  397.                     int med = (r + l) / 2;
  398.                     if (b[med].fi >= a[v[i].se.fi].fi)
  399.                         r = med;
  400.                     else
  401.                         l = med;
  402.                 }
  403.                 line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
  404.                 x2 = a[v[i].se.fi].fi;
  405.                 t2b = l;
  406.                 t2a = v[i].se.fi;
  407.                 y2 = (-l1.a * (ld)(a[v[i].se.fi].fi) - l1.c) / l1.b + dy;
  408.             }
  409.             else
  410.             {
  411.                 int l = 0, r = n - 1;
  412.                 while(r - l > 1)
  413.                 {
  414.                     int med = (r + l) / 2;
  415.                     if (a[med].fi >= b[v[i].se.fi].fi)
  416.                         r = med;
  417.                     else
  418.                         l = med;
  419.                 }
  420.                 line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
  421.                 x2 = b[v[i].se.fi].fi;
  422.                 t2a = l;
  423.                 t2b = v[i].se.fi;
  424.                 y2 = (-l1.a * (ld)(b[v[i].se.fi].fi) - l1.c) / l1.b;
  425.             }
  426.             i--;
  427.             c.clear();
  428.             c.push_back(makePoint(x1, y1));
  429.             for (int j = t1a; j <= t2a; j++)
  430.                 c.push_back(makePoint(a[j].fi, a[j].se));
  431.             c.push_back(makePoint(x2, y2));
  432.             for (int j = t2b; j >= t1b; j--)
  433.                 c.push_back(makePoint(b[j].fi, (ld)(b[j].se) + dy));
  434.             if (f(c) > eps)
  435.                 answ++;
  436.         }
  437.         best = answ;
  438.     }
  439.     cout << best;
  440.     return 0;
  441. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement