Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <ctime>
- #include <vector>
- #include <queue>
- #include <bitset>
- #include <cmath>
- #include <time.h>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <stdlib.h>
- #include <deque>
- #include <iomanip>
- #include <complex>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define _GLIBCXX_DEBUG
- #define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define all(v) v.begin(), v.end()
- #define randInt ((rand() << 15) | rand())
- #define For(i, n) for (int i = 0; i < n; i++)
- #define whatIs(x) cout << #x << " is " << x << endl
- #define in(s) freopen(s, "r", stdin)
- #define out(s) freopen(s, "w", stdout)
- #define mp(x, y) make_pair(x, y)
- #define fi first
- #define se second
- int nod(int a, int b)
- {
- return a ? nod(b % a, a) : b;
- }
- int nok(int a, int b)
- {
- return a / nod(a, b) * b;
- }
- string intToStr(ll n)
- {
- return n ? intToStr(n / 10) + (char)('0' + n % 10) : "";
- }
- long long sum(vector<int> v)
- {
- int ans = 0;
- For(i, v.size())
- ans += v[i];
- return ans;
- }
- bool prime(int n)
- {
- if (n == 1)
- return false;
- for (int i = 2; i <= sqrt(n); i++)
- if (n % i == 0)
- return false;
- return true;
- }
- bool letter(char c)
- {
- return 'a' <= c && c <= 'z';
- }
- bool LETTER(char c)
- {
- return 'A' <= c && c <= 'Z';
- }
- bool digit(char c)
- {
- return ('0' <= c && c <= '9');
- }
- ll stringToInt(string s)
- {
- ll ans = 0;
- for (int i = 0; i < s.size(); i++)
- ans = 10 * ans + digit(s[i]);
- return ans;
- }
- const ld pi = 3.141592653589793238462643383279;
- const ld eps = 1e-8;
- const ld zero = 0;
- const ll null = 0;
- const ll INF = 1e18;
- //const int INF = 1e9;
- const ll MOD = 1000000007;
- const int BIG = 1e9;
- const int alf = 26;
- const int MAXN = 200001;
- const int MAXM = 1001;
- const int dx[4] = {-1, 0, 1, 0};
- const int dy[4] = {0, 1, 0, -1};
- const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
- const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
- const string alphabet = "abcdefghijklmnopqrstuvwxyz";
- const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
- struct point
- {
- ld x;
- ld y;
- };
- struct line
- {
- ld a, b, c;
- };
- ld dist(point a, point b)
- {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- point makePoint(ld x, ld y)
- {
- point p;
- p.x = x;
- p.y = y;
- return p;
- }
- line makeLine(ld a, ld b, ld c)
- {
- line ans;
- ans.a = a;
- ans.b = b;
- ans.c = c;
- return ans;
- }
- line makeLine(point A, point B)
- {
- line l;
- l.a = A.y - B.y;
- l.b = B.x - A.x;
- l.c = -l.a * A.x - l.b * A.y;
- return l;
- }
- bool linesParallel(line l1, line l2)
- {
- return l1.a * l2.b == l2.a * l1.b;
- }
- point linesCross(line l1, line l2)
- {
- point p;
- p.y = (l1.a * l2.c - l2.a * l1.c) / (l2.a * l1.b - l1.a * l2.b);
- if (l1.a != 0)
- p.x = (-l1.b * p.y - l1.c) / l1.a;
- else
- p.x = (-l2.b * p.y - l2.c) / l2.a;
- return p;
- }
- ld f(vector<point> a)
- {
- if (a.size() < 3)
- return (ld)(0);
- ld ans = 0;
- for (int i = 0; i < a.size(); i++)
- ans += (a[(i + 1) % (int)(a.size())].x - a[i].x) * (a[(i + 1) % (int)(a.size())].y + a[i].y) / 2;
- return abs(ans);
- }
- vector< pair<int, int> > a, b;
- vector< pair< int, pair<int, int> > > v;
- vector<int> ans, ans2;
- vector<point> c;
- ld epsilon = 1e-10;
- int main()
- {
- fastRead;
- int n, m;
- cin >> n >> m;
- a.resize(n);
- b.resize(m);
- for (int i = 0; i < n; i++)
- cin >> a[i].fi >> a[i].se;
- for (int i = 0; i < m; i++)
- cin >> b[i].fi >> b[i].se;
- ld dy = 1e9;
- for (int i = 0; i < n; i++)
- {
- int l = 0, r = m - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= a[i].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
- ld y = (-l1.a * (ld)(a[i].fi) - l1.c) / l1.b;
- if (abs(abs((ld)(a[i].se) - y) - dy) < epsilon)
- ans.push_back(i);
- else if (abs((ld)(a[i].se) - y) < dy)
- {
- ans.clear();
- ans.push_back(i);
- dy = abs((ld)(a[i].se) - y);
- }
- }
- int answ = 0;
- if (ans.size() > 0 && ans[0] != 0)
- answ++;
- if (ans.size() > 0 && ans[ans.size() - 1] != n - 1)
- answ++;
- for (int i = 0; i < (int)(ans.size()) - 1; i++)
- if (ans[i] != ans[i + 1] - 1)
- answ++;
- else
- {
- int l = 0, r = m - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= a[ans[i]].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
- ld x1 = a[ans[i]].fi;
- int t1 = l;
- ld y1 = (-l1.a * (ld)(a[ans[i]].fi) - l1.c) / l1.b;
- l = 0;
- r = m - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= a[ans[i + 1]].fi)
- r = med;
- else
- l = med;
- }
- l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
- ld x2 = a[ans[i + 1]].fi;
- int t2 = l;
- ld y2 = (-l1.a * (ld)(a[ans[i + 1]].fi) - l1.c) / l1.b;
- c.clear();
- c.push_back(makePoint(x1, y1));
- for (int j = t1 + 1; j <= t2; j++)
- c.push_back(makePoint(b[j].fi, b[j].se));
- c.push_back(makePoint(x2, y2));
- if (f(c) > eps)
- answ++;
- }
- int best = answ;
- ans2 = ans;
- ans.clear();
- bool ok = false;
- for (int i = 0; i < m; i++)
- {
- int l = 0, r = n - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (a[med].fi >= b[i].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
- ld y = (-l1.a * (ld)(b[i].fi) - l1.c) / l1.b;
- if (abs(abs((ld)(b[i].se) - y) - dy) < epsilon)
- ans.push_back(i);
- else if (abs((ld)(b[i].se) - y) < dy)
- {
- ok = true;
- ans.clear();
- ans.push_back(i);
- dy = abs((ld)(b[i].se) - y);
- }
- }
- answ = 0;
- if (ans.size() > 0 && ans[0] != 0)
- answ++;
- if (ans.size() > 0 && ans[ans.size() - 1] != m - 1)
- answ++;
- for (int i = 0; i < (int)(ans.size()) - 1; i++)
- if (ans[i] != ans[i + 1] - 1)
- answ++;
- else
- {
- int l = 0, r = n - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (a[med].fi >= b[ans[i]].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
- ld x1 = b[ans[i]].fi;
- int t1 = l;
- ld y1 = (-l1.a * (ld)(b[ans[i]].fi) - l1.c) / l1.b;
- l = 0;
- r = n - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= b[ans[i + 1]].fi)
- r = med;
- else
- l = med;
- }
- l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
- ld x2 = b[ans[i + 1]].fi;
- int t2 = l;
- ld y2 = (-l1.a * (ld)(b[ans[i + 1]].fi) - l1.c) / l1.b;
- c.clear();
- c.push_back(makePoint(x1, y1));
- for (int j = t1 + 1; j <= t2; j++)
- c.push_back(makePoint(a[j].fi, a[j].se));
- c.push_back(makePoint(x2, y2));
- if (f(c) > eps)
- answ++;
- }
- if (ok)
- best = answ;
- else if (ans.size() > 0)
- {
- for (int i = 0; i < ans2.size(); i++)
- v.push_back({a[ans2[i]].fi, {ans2[i], 1}});
- for (int i = 0; i < ans.size(); i++)
- v.push_back({b[ans[i]].fi, {ans[i], 2}});
- sort(v.begin(), v.end());
- answ = 0;
- if (v.size() > 0 && v[0].se.fi != 0)
- answ++;
- 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))
- answ++;
- for (int i = 0; i < (int)(v.size()) - 1; i++)
- {
- ld x1, y1, x2, y2;
- int t1a, t1b, t2a, t2b;
- if (v[i].se.se == 1)
- {
- int l = 0, r = m - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= a[v[i].se.fi].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
- x1 = a[v[i].se.fi].fi;
- t1b = l + 1;
- t1a = v[i].se.fi;
- y1 = (-l1.a * (ld)(a[v[i].se.fi].fi) - l1.c) / l1.b + dy;
- }
- else
- {
- int l = 0, r = n - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (a[med].fi >= b[v[i].se.fi].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
- x1 = b[v[i].se.fi].fi;
- t1a = l + 1;
- t1b = v[i].se.fi;
- y1 = (-l1.a * (ld)(b[v[i].se.fi].fi) - l1.c) / l1.b;
- }
- i++;
- if (v[i].se.se == 1)
- {
- int l = 0, r = m - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (b[med].fi >= a[v[i].se.fi].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(b[l].fi, b[l].se), makePoint(b[l + 1].fi, b[l + 1].se));
- x2 = a[v[i].se.fi].fi;
- t2b = l;
- t2a = v[i].se.fi;
- y2 = (-l1.a * (ld)(a[v[i].se.fi].fi) - l1.c) / l1.b + dy;
- }
- else
- {
- int l = 0, r = n - 1;
- while(r - l > 1)
- {
- int med = (r + l) / 2;
- if (a[med].fi >= b[v[i].se.fi].fi)
- r = med;
- else
- l = med;
- }
- line l1 = makeLine(makePoint(a[l].fi, a[l].se), makePoint(a[l + 1].fi, a[l + 1].se));
- x2 = b[v[i].se.fi].fi;
- t2a = l;
- t2b = v[i].se.fi;
- y2 = (-l1.a * (ld)(b[v[i].se.fi].fi) - l1.c) / l1.b;
- }
- i--;
- c.clear();
- c.push_back(makePoint(x1, y1));
- for (int j = t1a; j <= t2a; j++)
- c.push_back(makePoint(a[j].fi, a[j].se));
- c.push_back(makePoint(x2, y2));
- for (int j = t2b; j >= t1b; j--)
- c.push_back(makePoint(b[j].fi, (ld)(b[j].se) + dy));
- if (f(c) > eps)
- answ++;
- }
- best = answ;
- }
- cout << best;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement