oj.uz

Submission #1032687

# Submission time Handle Problem Language Result Execution time Memory
1032687 2024-07-24T06:12:20 Z caterpillow Relay (COI16_relay) C++17
0 / 100
 37 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename... Args> // tuples
ostream& operator<<(ostream& os, tuple<Args...> t) { 
    apply([&](Args... args) { string dlm = "{"; ((os << dlm << args, dlm = ", "), ...); }, t);
    return os << "}";
}

template<typename T, typename V> // pairs
ostream& operator<<(ostream& os, pair<T, V> p) { return os << "{" << p.f << ", " << p.s << "}"; }

template<class T, class = decltype(begin(declval<T>()))> // iterables
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& os, const T& v) {
    string dlm = "{";
    for (auto& i : v) os << dlm << i, dlm = ", ";
    return os << "}";  
}

template <typename T, typename... V>
void printer(string pfx, const char *names, T&& head, V&& ...tail) {
    int i = 0;
    while (names[i] && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if (is_str) cerr << " " << head;
    else cerr << pfx, cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) printer(is_str ? "" : ",", names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) printer(to_string(__LINE__) + ": ", #__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

brute force all the points that will directly receive your initial message

for all the other points, find the "sight lines" that are bound by the convex polygon 
and check whether there are any points above/below it

    given a point (a, b) and a sight line y = mx + c
    (a, b) will be above the sight line if b >= m * a + c
    rearranged gives -c >= m * a - b
    checking whether a point is below is -c <= m * a - b, or c >= b - m * a (so we can use the same ds)
    

*/

pl operator+(const pl& a, const pl& b) {
    return {a.f + b.f, a.s + b.s};
}

pl operator-(const pl& a, const pl& b) {
    return {a.f - b.f, a.s - b.s};
}

ll operator*(const pl& a, const pl& b) {
    return a.f * b.s - a.s * b.f; // cross product
}

ll dot(const pl& a, const pl& b) {
    return a.f * b.f + a.s * b.s;
}

bool comp(const pl& a, const pl& b) {
    return a * b < 0;
}

struct Line {
    pl s, t;
};

int poop(ll x) {
    if (x == 0) return 0;
    if (x > 0) return 1;
    return -1;
}

bool inter(pl pos, pl dir, Line line) {
    pl x = line.s - pos;
    pl y = line.t - pos;
    int b1 = poop(x * dir);
    int b2 = poop(y * dir);
    bool f1 = (b1 * b2) < 0; // this means its like either pointing between x and y, or the wrong way
    bool f2 = (dot(x, dir) > 0) || (dot(y, dir) > 0); // i think this means they are facing the right way?
    return f1 && f2;
}

int n, m;
vt<pl> pts;
vt<pl> hull;
vt<Line> edges;

// clockwise, counter-clockwise
// pair<pl, pl> get_sight(pl pos) {
//     nth_element(hull.begin(), hull.begin(), hull.end(), comp);
//     pl cw = hull[0];
//     nth_element(hull.begin(), hull.end() - 1, hull.end());
//     pl ccw = hull.back();

//     return {cw, ccw};
// }

bool can_see(pl x, pl y) {
    pl dir = y - x;
    for (auto& l : edges) {
        if (inter(x, dir, l)) {
            return false;
        }
    }
    F0R (i, m) {
        if (inter(x, dir, {hull[i], hull[(i + 2) % m]})) {
            return false;
        }
    }
    return true;
}

vt<vt<int>> adj;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n;
    pts.resize(n); 
    F0R (i, n) cin >> pts[i].f >> pts[i].s;
    cin >> m;
    hull.resize(m);
    F0R (i, m) cin >> hull[i].f >> hull[i].s;
    edges.resize(m);
    F0R (i, m) edges[i] = {hull[i], hull[(i + 1) % m]};
    
    adj.resize(n);
    F0R (i, n) {
        FOR (j, i + 1, n) {
            if (can_see(pts[i], pts[j])) adj[i].pb(j), adj[j].pb(i);
        }
    }
    vt<int> good(n);
    good[0] = 1;
    for (int u : adj[0]) {
        good[u] = true;
        for (int v : adj[u]) {
            good[v] = true;
        }
    }
    cout << accumulate(all(good), -1) << endl;
}

Compilation message

relay.cpp:143:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  143 | main() {
      | ^~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Output is correct
2 Correct 37 ms 600 KB Output is correct
3 Correct 28 ms 604 KB Output is correct
4 Correct 28 ms 604 KB Output is correct
5 Correct 18 ms 604 KB Output is correct
6 Incorrect 18 ms 524 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Output is correct
2 Correct 37 ms 600 KB Output is correct
3 Correct 28 ms 604 KB Output is correct
4 Correct 28 ms 604 KB Output is correct
5 Correct 18 ms 604 KB Output is correct
6 Incorrect 18 ms 524 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Output is correct
2 Correct 37 ms 600 KB Output is correct
3 Correct 28 ms 604 KB Output is correct
4 Correct 28 ms 604 KB Output is correct
5 Correct 18 ms 604 KB Output is correct
6 Incorrect 18 ms 524 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Output is correct
2 Correct 37 ms 600 KB Output is correct
3 Correct 28 ms 604 KB Output is correct
4 Correct 28 ms 604 KB Output is correct
5 Correct 18 ms 604 KB Output is correct
6 Incorrect 18 ms 524 KB Output isn't correct
7 Halted 0 ms 0 KB -