Submission #220582

# Submission time Handle Problem Language Result Execution time Memory
220582 2020-04-08T06:12:49 Z toxic_hack Park (BOI16_park) C++14
100 / 100
798 ms 50140 KB
/*
    Imagine a rectangle something like this 
            3
       _____________
      |             |
    0 |             | 2
      |_____________|   
            1
    

    now to go from the corner 1 to corner 2
    then the connections from (1 to 0), (1 to 3) and (1, 2) should not be blocked.

    how to check if a particular path is blocked?

    add an edge between two circles if the distance between them is less than the radius of the 
    of the visitor.

    now can see the blocks and see if the visitor will reach anywhere with a bunch of conditions

    to handle multiple queries sort all the edges and then keep adding them in DSU

    once two sides of rectangle are in the same component then we know that the max radius of the visitor that can pass through this connection.

    see implementation of the details.
*/

// g++ -std=c++14

/*

Today might be the chance to grasp the chance to let your talent bloom.
May be tomorrow, the day after, or next year...
May be even when you are 30. I'm not sure if physique has anything to do with it
but if you think that it will never come, it probably never will.

- Tooru Oikawa.

*/


#include<bits/stdc++.h>

typedef long long ll;
typedef long double lld;
using namespace std;

#define endl "\n"
#define fi first
#define se second
#define MEMS(a,b) memset(a,b,sizeof(a))
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define all(c) c.begin(),c.end()
#define pii pair<int, int>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	uniform_int_distribution<int> uid(l, r);
	return uid(rng);
}

#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)
template<typename S, typename T>
ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;}

template<typename T>
ostream& operator<<(ostream& out,vector<T> const& v){
ll l=v.size();for(ll i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}

template <typename T>
ostream &operator<<(ostream &out, set<T> const &v) {
    for (auto i = v.begin(); i != v.end(); i++)
        out << (*i) << ' ';
    return out;
}
template <typename T>
ostream &operator<<(ostream &out, multiset<T> const &v) {
    for (auto i = v.begin(); i != v.end(); i++)
        out << (*i) << ' ';
    return out;
}
template <typename T, typename V>
ostream &operator<<(ostream &out, map<T, V> const &v) {
    for (auto i = v.begin(); i != v.end(); i++)
        out << "\n" << (i->first) <<  ":"  << (i->second);
    return out;
}

template<typename T>
void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}

template<typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}

#define int ll

const long double eps = 1e-12;
const long double infl = 1e20;

template <class T>
inline int sgn(const T & x) {
	return (x > eps) - (x < -eps);
}
template <class T>
struct Point {
 	T x, y;

	Point() : x(0), y(0) {

	}

	Point(const T & x, const T & y) : x(x), y(y) {

	}

	long double length() const {
		return sqrtl(x * x + y * y);
	}

	T length2() const {
		return x * x + y * y;
	}

	long double distance(const Point & rhs) const {
		return (rhs - *this).length();
	}

 	T cross(const Point & lhs, const Point & rhs) const {
		return (lhs - *this) * (rhs - *this);
	}

	T dot(const Point & lhs, const Point & rhs) const {
		return (lhs - *this) & (rhs - *this);
	}

	long double distance_to_line(const Point & p, const Point & q) const {
		if (p == q) return distance(p);
		else return fabsl(cross(p, q) / p.distance(q));
	}

	long double distance_to_segment(const Point & p, const Point & q) const {
		if (p == q) return distance(p);
		else if (p.dot(q, *this) < 0) return distance(p);
		else if (q.dot(p, *this) < 0) return distance(q);
		else return distance_to_line(p, q);
	}

	bool on_line(const Point & p, const Point & q) const {
		return sgn(cross(p, q)) == 0;
	}

	bool on_halfline(const Point & p, const Point & q, const bool & inclusive = true) const {
		if (*this == p) return inclusive;
		else return on_line(p, q) && sgn(p.dot(q, *this)) >= 0;
	}

	bool on_segment(const Point & p, const Point & q, const bool & inclusive = true) const {
		if (*this == p || *this == q) return inclusive;
		else return on_line(p, q) && sgn(dot(p, q)) <= 0;
	}

	bool in_triangle(const Point & u, const Point & v, const Point & w, const bool & inclusive = true) const {
		Point p[3] = {u, v, w};
		if (sgn(u.cross(v, w)) < 0) reverse(p, p + 3);
		for (int i = 0; i < 3; i++) {
			if (on_segment(p[i], p[(i + 1) % 3])) return inclusive;
			else if (sgn(cross(p[i], p[(i + 1) % 3])) < 0) return false;
		}
		return true;
	}

	bool in_angle(const Point & o, const Point & p, const Point & q, const bool & inclusive = true) const {
		if (on_halfline(o, p) || on_halfline(o, q)) return inclusive;
		int vs = sgn(o.cross(p, q)), ss = sgn(o.dot(p, q));
		if (vs == 0 && ss > 0) return false;
		int vp = sgn(o.cross(p, *this)), vq = sgn(o.cross(*this, q));
		if (sgn(o.cross(p, q)) >= 0) return vp > 0 && vq > 0;
		else return vp > 0 || vq > 0;
	}

	Point operator + (const Point & rhs) const {// returns a+b(vector addition)
		return Point(x + rhs.x, y + rhs.y);
	}

	Point operator - (const Point & rhs) const {// Returns a-b(vector subtraction)
		return Point(x - rhs.x, y - rhs.y);
	}

	T operator * (const Point & rhs) const { 	// cross product
		return x * rhs.y - y * rhs.x;
	}

	T operator & (const Point & rhs) const { 	// dot product
		return x * rhs.x + y * rhs.y;
	}

	Point operator * (const T & rhs) const {	// multiplication with constant
		return Point(x * rhs, y * rhs);
	}

	Point operator / (const T & rhs) const {	// division with constant
		return Point(x / rhs, y / rhs);
	}

	bool operator == (const Point & rhs) const {// returns true if points are located at the same point.
		return x == rhs.x && y == rhs.y;
	}

	bool operator != (const Point & rhs) const {// returns true if points are not located at same point.
		return x != rhs.x || y != rhs.y;
	}

	inline int quadrant() const {				// returns quadrant defined from 0 to 7 (-1 if origin). Used in operator <
		if (x == 0 && y == 0) return -1;
		else if (x < 0 && y < 0) return 0;
		else if (x == 0 && y < 0) return 1;
		else if (x > 0 && y < 0) return 2;
		else if (x > 0 && y == 0) return 3;
		else if (x > 0 && y > 0) return 4;
		else if (x == 0 && y > 0) return 5;
		else if (x < 0 && y > 0) return 6;
		else return 7;
	}

	bool operator < (const Point & rhs) const {	//used for sorting the points in counter clockwise order.
		int lq = quadrant(), rq = rhs.quadrant();
		if (lq != rq) {
			return lq < rq;
		} else {
			int s = sgn(*this * rhs);
			return s != 0 ? s > 0 : sgn(length2() - rhs.length2()) < 0;
		}
	}
};
const int N = 2200;

struct circle {
    int x, y, r;
};
int n, m, w, h;
vector<circle> arr;

int inter (int r, int x, int y, int r2, int x2, int y2){
    if (1LL * (r + r2) * (r + r2) > 1LL * (x - x2) * (x - x2) + 1LL * (y - y2) * (y - y2))
        return 1;
    return 0;
}

int get_dist(int i, int j) {
    int l = 0, r = 1e9;
    int mid, ans = 0;
    while (l <= r) {    
        mid = (l + r) / 2;
        if (inter(arr[i].r + mid, arr[i].x, arr[i].y, arr[j].r + mid, arr[j].x, arr[j].y)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return 2 * ans;
}

int parent[N];
int size[N];

void make_set(int x) {
    parent[x] = x;
    size[x] = 1;
}

int find_set(int v) {
    if(v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if(a != b) {
        if(size[a] < size[b]) {
            swap(a,b);
        }
        parent[b] = a;
        size[a] += size[b];
    }
}


int solve() {
    cin >> n >> m >> w >> h;
    for (int i = 0; i < n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        arr.push_back({x, y, r});
    }

    vector<pair<int, pii>> edges;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            auto dist = (int)get_dist(i, j);
            edges.push_back({dist, {i + 1, j + 1}});
        }
    }
    Point<lld> lb, rb, lt, rt;
    lb.x = 0, lb.y = 0;
    rb.x = w, rb.y = 0;
    lt.x = 0, lt.y = h;
    rt.x = w, rt.y = h;
    vector<pair<Point<lld>, Point<lld>>> corners = {{lb, lt}, {lb, rb}, {rt, rb}, {lt, rt}} ;
    for (int i = 0; i < n; i++) {
        Point<lld> p;
        p.x = arr[i].x;
        p.y = arr[i].y;
        for (int j = 0; j < 4; j++) {
            int dist = p.distance_to_line(corners[j].first, corners[j].second);
            edges.push_back({dist - arr[i].r, {i + 1, n + 1 + j}});
        }
    }

    for (int i = 1; i <= n + 4; i++) {
        make_set(i);
    }

    vector<vector<int>> mat(4, vector<int> (4, -1));

    sort(all(edges));
    // tr(edges);
    lld curr = 0.0;
    for (auto &e : edges) {
        curr = e.first;
        union_sets(e.second.first, e.second.second);
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                int x = find_set(n + i + 1);
                int y = find_set(n + j + 1);
                if (x == y && (mat[i][j] < 0)) {
                    mat[i][j] = (int)curr;
                    mat[j][i] = (int)curr;
                }
            }
        }
    }
    for (int i_ = 0; i_ < m; i_++) {
        int rad, pos;
        cin >> rad >> pos;
        rad *= 2;
        pos--;
        string ans = "";
        if (pos == 0) {
            if (rad < min({mat[0][3], mat[0][2], mat[0][1]})) {
                ans += '4';
            }
            if (rad < min({mat[0][2], mat[3][2], mat[0][1], mat[1][3]})) {
                ans += '3';
            }
            if (rad < min({mat[1][2], mat[3][1], mat[0][1]})) {
                ans += '2';
            }
            ans += '1';
        } else if (pos == 1) {
            if (rad < min({mat[1][2], mat[3][1], mat[0][1]})) {
                ans += '1';
            }
            if (rad < min({mat[1][2], mat[3][2], mat[0][2]})) {
                ans += '3';
            }
            if (rad < min({mat[1][2], mat[3][0], mat[0][2], mat[1][3]})) {
                ans += '4';
            }
            ans += '2';
        } else if (pos == 2) {
            if (rad < min({mat[0][2], mat[3][2], mat[0][1], mat[1][3]})) {
                ans += '1';
            }
            if (rad < min({mat[1][2], mat[3][2], mat[0][2]})) {
                ans += '2';
                // tr(mat[2]);
            }
            if (rad < min({mat[1][3], mat[3][2], mat[0][3]})) {
                // tr(rad, mat[3]);
                ans += '4';
            }
            ans += '3';
        } else {
            if (rad < min({mat[0][3], mat[0][2], mat[0][1]})) {
                ans += '1';
            }
            if (rad < min({mat[1][2], mat[3][0], mat[0][2], mat[1][3]})) {
                ans += '2';
            }
            if (rad < min({mat[1][3], mat[3][2], mat[0][3]})) {
                ans += '3';
            }
            ans += '4';
        }
        sort(all(ans));
        cout << ans << endl;
    }
    return 0;
}

int32_t main(){ _
    int t;
    // cin >> t;
    t = 1;
    while (t--) solve();
}
# Verdict Execution time Memory Grader output
1 Correct 765 ms 50060 KB Output is correct
2 Correct 780 ms 50012 KB Output is correct
3 Correct 766 ms 49884 KB Output is correct
4 Correct 768 ms 49884 KB Output is correct
5 Correct 778 ms 49884 KB Output is correct
6 Correct 765 ms 49956 KB Output is correct
7 Correct 673 ms 49884 KB Output is correct
8 Correct 679 ms 50108 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 2416 KB Output is correct
2 Correct 44 ms 2548 KB Output is correct
3 Correct 42 ms 2292 KB Output is correct
4 Correct 42 ms 2420 KB Output is correct
5 Correct 43 ms 2420 KB Output is correct
6 Correct 43 ms 2428 KB Output is correct
7 Correct 37 ms 1784 KB Output is correct
8 Correct 36 ms 1916 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 765 ms 50060 KB Output is correct
2 Correct 780 ms 50012 KB Output is correct
3 Correct 766 ms 49884 KB Output is correct
4 Correct 768 ms 49884 KB Output is correct
5 Correct 778 ms 49884 KB Output is correct
6 Correct 765 ms 49956 KB Output is correct
7 Correct 673 ms 49884 KB Output is correct
8 Correct 679 ms 50108 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 42 ms 2416 KB Output is correct
12 Correct 44 ms 2548 KB Output is correct
13 Correct 42 ms 2292 KB Output is correct
14 Correct 42 ms 2420 KB Output is correct
15 Correct 43 ms 2420 KB Output is correct
16 Correct 43 ms 2428 KB Output is correct
17 Correct 37 ms 1784 KB Output is correct
18 Correct 36 ms 1916 KB Output is correct
19 Correct 798 ms 50012 KB Output is correct
20 Correct 797 ms 50012 KB Output is correct
21 Correct 795 ms 50012 KB Output is correct
22 Correct 793 ms 50020 KB Output is correct
23 Correct 792 ms 50140 KB Output is correct
24 Correct 702 ms 50140 KB Output is correct