Submission #1032687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032687		caterpillow	Relay (COI16_relay)	C++17	0 / 100	37 ms	604 KiB

relay

#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 (stderr)

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

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43