| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1032676 |
2024-07-24T06:05:46 Z |
caterpillow |
Relay (COI16_relay) |
C++17 |
|
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() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
