//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
int w, h, c, n, vis[MAXN];
ll xg, yg;
pll pos[MAXN], tmp[MAXN];
struct sweep {
int type, ind; // 0->start, 1->end, 2->query
ll x, y;
} a[MAXN];
int sgn(ll x) {
if (x == 0) return 0;
return x > 0 ? 1 : -1;
}
int ccw(pll x, pll y, pll z) {
ll ret = (y.fi-x.fi) * (z.se-x.se) - (y.se-x.se) * (z.fi-x.fi);
return sgn(ret);
}
pll corner[4];
pll f(pll from, pll to, int t) {
ll dx = to.fi - from.fi, dy = to.se - from.se;
if (dx == 0) {
if (dy > 0)
return mp(to.fi, h);
return mp(to.fi, 0);
}
if (dy == 0) {
if (dx > 0)
return mp(w, to.se);
return mp(0, to.se);
}
for (int i = 0; i < 4; i++) {
int o1 = ccw(from, to, corner[i]);
int o2 = ccw(from, to, corner[(i+1)%4]);
if (o1 == 0 && sgn(corner[i].fi - from.fi) == sgn(dx) && sgn(corner[i].se - from.se) == sgn(dy))
return corner[i];
if (o1 != -1) continue;
if (o2 != 1) continue;
if (i == 1 || i == 3) {
ll lo = 0, hi = h;
int sgn = (i == 1) ? -1 : 1;
while (lo <= hi) {
ll mi = (lo+hi) / 2;
o1 = ccw(from, to, mp(corner[i].fi, mi)) * sgn;
if (o1 == 0) return mp(corner[i].fi, mi);
if (o1 > 0)
lo = mi + 1;
else
hi = mi - 1;
}
if ((t == 0 && i == 3) || (t == 1 && i == 1))
return mp(corner[i].fi, lo-1);
return mp(corner[i].fi, lo);
} else {
ll lo = 0, hi = w;
int sgn = (i == 0) ? -1 : 1;
while (lo <= hi) {
ll mi = (lo+hi) / 2;
o1 = ccw(from, to, mp(mi, corner[i].se)) * sgn;
if (o1 == 0) return mp(mi, corner[i].se);
if (o1 > 0)
lo = mi + 1;
else
hi = mi - 1;
}
if ((t == 0 && i == 0) || (t == 1 && i == 2))
return mp(lo, corner[i].se);
return mp(lo-1, corner[i].se);
}
}
}
int main() {
scanf("%d %d %lld %lld %d", &w, &h, &xg, &yg, &c);
corner[0] = mp(0,0);
corner[1] = mp(w,0);
corner[2] = mp(w,h);
corner[3] = mp(0,h);
for (int i = 0; i < c; i++) {
a[i].type = 2;
a[i].ind = i+1;
scanf("%lld %lld", &a[i].x, &a[i].y);
}
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld %lld", &pos[i].fi, &pos[i].se);
for (int i = 1; i <= n; i++) {
pii l=mp(0,0), r=mp(0,0);
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
pll cur = mp(2 * pos[i].fi - pos[j].fi, 2 * pos[i].se - pos[j].se);
tmp[j] = cur;
int o = ccw(pos[i], mp(xg, yg), cur);
if (o > 0) {
if (l.fi == 0)
l = mp(j, j);
else {
if (ccw(pos[i], cur, tmp[l.fi]) > 0)
l.fi = j;
if (ccw(pos[i], cur, tmp[l.se]) < 0)
l.se = j;
}
} else {
if (r.fi == 0)
r = mp(j, j);
else {
if (ccw(pos[i], cur, tmp[r.fi]) < 0)
r.fi = j;
if (ccw(pos[i], cur, tmp[r.se]) > 0)
r.se = j;
}
}
}
//cerr << "add from: " << pos[i].fi << " " << pos[i].se << "\n";
if (r.fi == 0) {
tmp[l.fi] = f(pos[i], tmp[l.fi], 0);
tmp[l.se] = f(pos[i], tmp[l.se], 1);
a[c++] = {0, i, tmp[l.fi].fi, tmp[l.fi].se};
a[c++] = {1, i, tmp[l.se].fi, tmp[l.se].se};
} else if (l.fi == 0) {
tmp[r.se] = f(pos[i], tmp[r.se], 0);
tmp[r.fi] = f(pos[i], tmp[r.fi], 1);
a[c++] = {0, i, tmp[r.se].fi, tmp[r.se].se};
a[c++] = {1, i, tmp[r.fi].fi, tmp[r.fi].se};
} else {
tmp[l.fi] = f(pos[i], tmp[l.fi], 0);
tmp[r.fi] = f(pos[i], tmp[r.fi], 1);
a[c++] = {0, i, tmp[l.fi].fi, tmp[l.fi].se};
a[c++] = {1, i, tmp[r.fi].fi, tmp[r.fi].se};
}
//cerr << a[c-2].type << " " << a[c-2].ind << " " << a[c-2].x << " " << a[c-2].y << "\n";
//cerr << a[c-1].type << " " << a[c-1].ind << " " << a[c-1].x << " " << a[c-1].y << "\n";
}
/*for (int i = 0; i < c; i++) {
cerr << i << " " << a[i].type << " " << a[i].ind << " " << a[i].x << " " << a[i].y << "\n";
}*/
sort(a, a + c, [](sweep l, sweep r) {
int o1 = ccw(mp(xg, yg), mp(xg+1,yg), mp(l.x, l.y));
int o2 = ccw(mp(xg, yg), mp(xg+1,yg), mp(r.x, r.y));
if (o1 == 0) {
if (l.x > xg) return true;
return o1 > o2;
}
if (o2 == 0) {
if (r.x > xg) return false;
return o1 > o2;
}
if (o1 != o2)
return o1 > o2;
o1 = ccw(mp(xg, yg), mp(l.x, l.y), mp(r.x, r.y));
if (o1 != 0) return o1 > 0;
if (l.type == 0) return true;
if (l.type == 1) return false;
if (r.type == 0) return false;
if (r.type == 1) return true;
return l.ind < r.ind;
});
/*cerr << "\n";
for (int i = 0; i < c; i++) {
cerr << i << " " << a[i].type << " " << a[i].ind << " " << a[i].x << " " << a[i].y << "\n";
}*/
vi ans;
int cnt = 0;
for (int i = 0; i < c; i++) {
if (a[i].type == 2) continue;
if (a[i].type == 1 && !vis[a[i].ind])
cnt++;
if (a[i].type == 0)
vis[a[i].ind] = 1;
else
vis[a[i].ind] ^= 1;
}
for (int i = 0; i < c; i++) {
if (a[i].type == 2) {
if (cnt == 0)
ans.pb(a[i].ind);
continue;
}
if (a[i].type == 1)
cnt--;
else
cnt++;
}
sort(ans.begin(), ans.end());
pri(ans.size());
for (int i: ans)
printf("%d ", i);
enl;
return 0;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:13:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
#define pri(n) printf("%d\n", (n))
~~~^
fangorn.cpp:224:2: note: in expansion of macro 'pri'
pri(ans.size());
^~~
fangorn.cpp: In function 'std::pair<long long int, long long int> f(std::pair<long long int, long long int>, std::pair<long long int, long long int>, int)':
fangorn.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
fangorn.cpp: In function 'int main()':
fangorn.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld %lld %d", &w, &h, &xg, &yg, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &a[i].x, &a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
fangorn.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &pos[i].fi, &pos[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
380 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
404 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
13 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
41 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
632 KB |
Output is correct |
| 2 |
Correct |
46 ms |
940 KB |
Output is correct |
| 3 |
Correct |
45 ms |
904 KB |
Output is correct |
| 4 |
Correct |
36 ms |
916 KB |
Output is correct |
