Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define lli long long int
- #define fi first
- #define se second
- #define sc scanf
- #define pr printf
- #define pb push_back
- #define mp make_pair
- #define fin freopen( "input.txt", "r", stdin );
- #define fout freopen( "output.txt", "w", stdout );
- const int N = 200200;
- using namespace std;
- struct point
- {
- long double x;
- long double y;
- };
- int n;
- int m;
- bool used[N];
- point a[N];
- point b[N];
- int orientation(point p, point q, point r)
- {
- long double val = (q.y - p.y) * (r.x - q.x) -
- (q.x - p.x) * (r.y - q.y);
- if (val == 0)
- return 0;
- return (val > 0)? 1: 2;
- }
- bool cmp(point a, point b)
- {
- return a.x < b.x;
- }
- long double dist(point a, point b)
- {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- int get_pos_a(long double x)
- {
- int l = 1,
- r = m;
- while(l < r){
- int mid = (l + r) / 2;
- if(x >= b[mid + 1].x)
- l = mid + 1;
- else
- r = mid;
- }
- return l;
- }
- int get_pos_b(long double x)
- {
- int l = 1,
- r = n;
- while(l < r){
- int mid = (l + r) / 2;
- if(x >= a[mid + 1].x)
- l = mid + 1;
- else
- r = mid;
- }
- return l;
- }
- int main()
- {
- //fin("input.txt");
- //fout("output.txt");
- ios_base::sync_with_stdio(0);
- cin >> n >> m;
- for(int i = 1; i <= n; i++)
- cin >> a[i].x >> a[i].y;
- for(int i = 1; i <= m; i++)
- cin >> b[i].x >> b[i].y;
- long double mn = 1e9;
- vector < point > va, vb;
- for(int i = 1; i <= n; i++){
- int l = get_pos_a(a[i].x);
- if(a[i].x == b[l].x)
- continue;
- long double le = 2,
- re = 1e9;
- for(int j = 0; j < 200; j++){
- long double me = (le + re) / 2.0;
- point p = {a[i].x, a[i].y - me};
- if(orientation(b[l], b[l + 1], p) == 1)
- re = me;
- else
- le = me;
- }
- vb.pb({a[i].x, a[i].y - (le + re) / 2.0});
- }
- for(int i = 1; i <= m; i++){
- int l = get_pos_b(b[i].x);
- if(a[l].x == b[i].x)
- continue;
- long double le = 2,
- re = 1e9;
- for(int j = 0; j < 200; j++){
- long double me = (le + re) / 2.0;
- point p = {b[i].x, b[i].y + me};
- if(orientation(a[l], a[l + 1], p) == 2)
- re = me;
- else
- le = me;
- }
- va.pb({b[i].x, b[i].y + (le + re) / 2.0});
- }
- for(auto p: va)
- a[++n] = p;
- for(auto p: vb)
- b[++m] = p;
- sort(a + 1, a + n + 1, cmp);
- sort(b + 1, b + m + 1, cmp);
- for(int i = 1; i <= n; i++)
- mn = min(mn, dist(a[i], b[i]));
- int cnt = 0;
- used[n + 1] = used[0] = true;
- for(int i = n; i >= 1; i--){
- if(dist(a[i], b[i]) - mn < 1e-4)
- used[i] = true;
- }
- for(int i = 1; i <= n; i++)
- if(used[i + 1] == false && used[i] == true && used[i - 1] == false)
- cnt++;
- for(int i = 2; i <= n; i++){
- if(used[i] == false){
- cout << cnt + 1 << endl;
- return 0;
- }
- }
- cout << 0 << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement