#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
template <typename T> struct Point {
T x, y;
Point() : x(0), y(0) {}
Point(T _x, T _y) : x(_x), y(_y) {}
Point operator+(const Point other) const {
return Point(x + other.x, y + other.y);
}
Point operator-(const Point other) const {
return Point(x - other.x, y - other.y);
}
Point operator*(const T lambda) const {
return Point(x * lambda, y * lambda);
}
Point operator/(const T lambda) const {
return Point(x / lambda, y / lambda);
}
bool operator<(const Point &other) const {
return tie(x, y) < tie(other.x, other.y);
}
bool operator==(const Point &other) const {
return tie(x, y) == tie(other.x, other.y);
}
bool operator>(const Point &other) const { return other < *this; }
bool operator!=(const Point &other) const { return !(*this == other); }
bool operator<=(const Point &other) const { return !(other < *this); }
bool operator>=(const Point &other) const { return other <= *this; }
friend ostream &operator<<(ostream &out, const Point &a) {
return out << a.x << " " << a.y;
}
friend istream &operator>>(istream &in, Point &a) { return in >> a.x >> a.y; }
friend T dot(const Point a, const Point b) { return a.x * b.x + a.y * b.y; }
friend T cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; }
friend T dis2(const Point a, const Point b) { return dot(b - a, b - a); }
};
using pt = Point<int>;
struct Angle {
int x, y;
int t;
Angle(int x, int y, int t = 0) : x(x), y(y), t(t) {}
Angle operator-(Angle b) const { return {x - b.x, y - b.y, t}; }
int half() const {
assert(x || y);
return y < 0 || (y == 0 && x < 0);
}
Angle t90() const { return {-y, x, t + (half() && x >= 0)}; }
Angle t180() const { return {-x, -y, t + half()}; }
Angle t360() const { return {x, y, t + 1}; }
};
bool operator<(Angle a, Angle b) {
// add a . dist2 () and b . dist2 () to also compare distances
return make_tuple(a.t, a.half(), a.y * (int)b.x) <
make_tuple(b.t, b.half(), a.x * (int)b.y);
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int w, h;
cin >> w >> h;
pt init;
cin >> init;
int nbCamps;
cin >> nbCamps;
vector<pt> camps(nbCamps);
for (pt &p : camps)
cin >> p;
int nbArbres;
cin >> nbArbres;
vector<pt> arbres(nbArbres);
for (pt &p : arbres)
cin >> p;
vector<int> sol(nbCamps);
iota(sol.begin(), sol.end(), 0);
for (int i = 0; i < nbArbres; ++i) {
vector<Angle> rays;
for (int j = 0; j < nbArbres; ++j)
if (i != j) {
pt p = arbres[i] - arbres[j];
rays.emplace_back(p.x, p.y);
rays.emplace_back(p.x, p.y, 1);
rays.emplace_back(p.x, p.y, -1);
}
sort(rays.begin(), rays.end());
for (auto [x, y, p] : rays)
dbg(x, y, p);
vector<int> nxtSol;
pt r = init - arbres[i];
Angle rayInit(r.x, r.y);
dbg(rayInit.x, rayInit.y);
auto findPos = [&](Angle a) {
int u = 0;
while (not(rays[u] < a and a < rays[u + 1]))
u++;
return u;
};
for (int c : sol) {
pt p = camps[c] - arbres[i];
Angle ray(p.x, p.y);
dbg(ray.x, ray.y);
/*int u = findPos(rayInit) % (nbArbres - 1);
int v = findPos(ray) % (nbArbres - 1);*/
int u = lower_bound(rays.begin(), rays.end(), rayInit) - rays.begin();
int v = lower_bound(rays.begin(), rays.end(), ray) - rays.begin();
u %= nbArbres - 1;
v %= nbArbres - 1;
dbg(u, v);
if (u == v)
nxtSol.push_back(c);
}
sol = nxtSol;
}
cout << sol.size() << endl;
for (int x : sol)
cout << x + 1 << ' ';
cout << endl;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:130:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
130 | for (auto [x, y, p] : rays)
| ^~~~~~~~~
fangorn.cpp:137:10: warning: variable 'findPos' set but not used [-Wunused-but-set-variable]
137 | auto findPos = [&](Angle a) {
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
2 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
212 KB |
Output is correct |
| 6 |
Correct |
5 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
11 ms |
340 KB |
Output is correct |
| 11 |
Correct |
12 ms |
364 KB |
Output is correct |
| 12 |
Correct |
13 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
389 ms |
524 KB |
Output is correct |
| 5 |
Correct |
81 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1675 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1958 ms |
812 KB |
Output is correct |
| 2 |
Execution timed out |
3074 ms |
1140 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
