oj.uz

답안 #1032676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032676 2024-07-24T06:05:46 Z caterpillow Relay (COI16_relay) C++17
0 / 100
 21 ms 692 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?
    dbg(f1, f2);
    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;
        }
    }
    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:139:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  139 | main() {
      | ^~~~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 13 ms 692 KB Output is correct
4 Correct 14 ms 624 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Incorrect 10 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 13 ms 692 KB Output is correct
4 Correct 14 ms 624 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Incorrect 10 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 13 ms 692 KB Output is correct
4 Correct 14 ms 624 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Incorrect 10 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 13 ms 692 KB Output is correct
4 Correct 14 ms 624 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Incorrect 10 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -