// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front
#define fr front
#define bc back
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void solve();
signed main() {
// freopen("input.inp","r",stdin);
fastio();
int tc = 1;
// cin >> tc;
fori(test, 1, tc) {
solve();
}
return 0;
}
//const ld pi = 4 * atan(1.0), eps = 1e-9;
#define int long long
//#define ll long long
const int maxn = 2e5 + 5, mod = 1e9 + 7;
int type;
int n, q, rep;
ii arr[maxn << 1];
#define ld long double
int cv(int x) {
if(!x) return 0;
if(x < 0) return -1;
return 1;
}
int cw(ii a, ii b, ii c) {
b.fi -= a.fi, c.fi -= a.fi;
b.se -= a.se, c.se -= a.se;
int a1 = cv(b.fi) * cv(c.se), a2 = cv(b.se) * cv(c.fi);
if(!a1 or !a2) return a1 < a2;
return (ld) b.fi * (c.se / abs(c.se)) / abs(c.fi) < (ld) b.se * (c.fi / abs(c.fi)) / abs(c.se);
}
void solve() {
// cout << cw(ii(0, 0), ii(0, 1), ii(1, 0)) << endl;
cin >> type;
cin >> n;
fori(i,1, n) {
cin >> arr[i].fi >> arr[i].se;
arr[i + n] = arr[i];
}
cin >> q;
fori(i,1, q) {
int x, y;
cin>> x >> y;
x = x ^ (type * rep * rep * rep);
y = y ^ (type * rep * rep * rep);
int lo = 2, hi = n;
ii qr(x, y);
while(lo < hi) {
int mi = lo + hi + 1 >> 1;
if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[1],arr[mi])) == 0 ) {
lo = mi;
}
else {
hi = mi - 1;
}
}
int temp = lo;
lo = 2, hi = temp;
while(lo < hi) {
int mi = lo + hi >> 1;
if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[mi], arr[mi + 1]) ) == 1) {
hi = mi;
}
else {
lo = mi + 1;
}
}
int ll = lo;
int rr;
if(temp == n) {
rr = 1;
}
else {
lo = temp + 1, hi = n;
while(lo < hi) {
int mi = lo + hi >> 1;
if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[mi], arr[mi + 1]) ) == 0) {
hi = mi;
}
else {
lo = mi + 1;
}
}
rr = lo;
}
if(cw(qr, arr[1], arr[2])) swap(ll, rr);
if(rr < ll) rr += n;
if(rr - ll < n / 2) cout << "DA", ++rep;
else cout << "NE";
cout << endl;
}
}
Compilation message
zvijezda.cpp: In function 'void solve()':
zvijezda.cpp:120:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
120 | int mi = lo + hi + 1 >> 1;
| ~~~~~~~~^~~
zvijezda.cpp:135:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | int mi = lo + hi >> 1;
| ~~~^~~~
zvijezda.cpp:154:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
154 | int mi = lo + hi >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
3 ms |
332 KB |
Output is correct |
| 8 |
Correct |
3 ms |
332 KB |
Output is correct |
| 9 |
Correct |
3 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
332 KB |
Output is correct |
| 11 |
Correct |
3 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
3 ms |
332 KB |
Output is correct |
| 8 |
Correct |
3 ms |
332 KB |
Output is correct |
| 9 |
Correct |
3 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
332 KB |
Output is correct |
| 11 |
Correct |
3 ms |
332 KB |
Output is correct |
| 12 |
Incorrect |
72 ms |
524 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
3532 KB |
Output is correct |
| 2 |
Incorrect |
190 ms |
3652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
